POJ1321 棋盘问题(dfs)

题目链接。

分析：

用 dfs 一行一行的搜索，col记录当前列是否已经放置。

AC代码如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cstring>
#include <queue>using namespace std;const int maxn = ;int n, k, cnt;
bool col[maxn];
char G[maxn][maxn];void dfs(int row, int num) {
    if(num == k) { cnt++; return ; }    if(row+ > n) return;    for(int j=; j<n; j++) {
        if(G[row][j] == '#') {
            if(!col[j]) {
                col[j] = true;
                dfs(row+, num+);
                col[j] = false;
            }
        }
    }    dfs(row+, num);
}int main() {    while(scanf("%d%d", &n, &k) == ) {
   　　 if(n == - && k == -) break;    　　memset(col, false, sizeof(col));   　　 for(int i=; i<n; i++) {
      　　  scanf("%s", G[i]);
    　　}    　　cnt = ;   　　 dfs(, ); 　　   printf("%d\n", cnt);
    }    return ;
}