欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ-1321棋盘问题(dfs)

程序员文章站 2022-05-20 20:49:15
...

图论dfs入门题,纯暴力,题目要求在所给棋盘中,将棋子放入‘#’的位置,且同一行同一列只能放置一个棋子。注意dfs中递归的方式。

  • 分别以每行棋子开始进行dfs遍历,最后将结果相加。

代码如下:

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctype.h>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <limits.h>
using namespace std;
const int N = 10;
char a[N][N];
int n, k, cnt, ans;
int vis[N];
void dfs(int x)
{
    if (cnt == k){
        ans++;
        return;
    }
    if (x == n){
        return;
    }
    for (int i = 0; i < n; i++){
        if (!vis[i] && a[x][i] == '#'){
            vis[i] = 1;
            cnt++;
            dfs(x + 1);
            cnt--;
            vis[i] = 0;
        }
    }
    dfs(x + 1);			//从下一行开始遍历
}

int main()
{
    while(~scanf("%d%d", &n, &k)){
        if (n == -1 && k == -1)
            break;
        for (int i = 0; i < n; i++){
            scanf("%s", a[i]); 
        }
        memset(vis, 0, sizeof(vis));
        ans = 0;
        cnt = 0;
        dfs(0);
        printf("%d\n", ans);
    }
    return 0;
}


// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
相关标签: dfs