碁盤問題POJ-1321(DFS)

碁盤問題POJ-1321

          （         ）      ，      。                            ，                 ，  k             C。 

Input入力には複数のテストデータが含まれています.各グループのデータの最初の行は2つの正の整数、n kであり、1つのスペースで区切られ、1つのn*nのマトリクス内に碁盤を記述し、駒を置く数を示す.n<=8,k<=nは−1−1で入力終了を示す.次のn行は、各行にn文字を有する碁盤の形状を示す.空白領域を表します(データは余分な空白行や空白列が現れないことを保証します).Outputは、各セットのデータに対して、1行の出力を与え、配置されたシナリオ数Cを出力する(データ保証C<2^31).Sample Input

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

Sample Output

2
1

タイトル:
1つのn*nの図を与えて、k個の駒と、#の上で駒を放して、1行ごとに1つの駒の方案の数だけあることを要求していくらあります
分析:
1枚だけ行えばいいので、配列に列をマークして、この列に駒があるかどうかを見て、dfsに下ります.
久しぶりに検索を书いて、今日最も简単なものを探してすべて书いていないで、本当にtmd料理は犬になりました
code:

#include 
#include 
#include 
using namespace std;
bool vis[20];//  i         
char mp[20][20];
int n,k,ans;
void dfs(int x,int s){// x ，    s   
    if(s == k){
        ans++;
        return;
    }
    for(int i = x; i < n; i++){
        for(int j = 0; j < n; j++){
            if(!vis[j] && mp[i][j] == '#'){
                vis[j] = 1;
                dfs(i+1,s+1);
                vis[j] = 0;
            }
        }
    }
}
int main(){
    while(~scanf("%d%d",&n,&k)){
        if(n == -1 && k == -1) break;
        for(int i = 0; i < n; i++){
            scanf("%s",mp[i]);
        }
        memset(vis,0,sizeof(vis));
        ans = 0;
        dfs(0,0);
        printf("%d
",ans);
    }
    return 0;
}