POJ1321 棋盘问题（DFS回溯）

题目链接

中文题。

#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
char pic[10][10];
bool jud[10][10];   //1代表棋盘
bool l[10];    //当前列是否已有棋子
int n, k, ans;
void dfs(int cur, int num){   //cur为当前行，num为已放棋子数目
    if(num == k){
        ans++;
        return;
    }
    if(cur == n) return;
    dfs(cur+1, num);
    for(int i = 0; i < n; i++){
        if(jud[cur][i] && !l[i]){
            l[i] = 1;
            dfs(cur+1, num+1);
            l[i] = 0;
        }
    }
}

int main(){
    //freopen("a.txt", "r", stdin);
    while(scanf("%d %d", &n, &k) != EOF){
        if(n == -1 && k == -1) break;
        memset(jud, 0, sizeof(jud));
        memset(l, 0, sizeof(l));
        for(int i = 0; i < n; i++)
            scanf("%s", pic[i]);
        ans = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(pic[i][j] == '#')
                    jud[i][j] = 1;
            }
        }
        dfs(0, 0);
        cout << ans << endl;
    }
    return 0;
}