【POJ1321】棋盘问题

本题传动门

本题知识点：深度优先搜索 + 枚举 + 回溯

题意是要求我们把棋子放在棋盘的'#'上，但不能把两枚棋子放在同一列或者同一行上，问摆好这k枚棋子有多少种情况。

我们可以一行一行地找，当在某一行上找到一个可放入的'#'后，就开始找下一行的'#'，如果下一行没有，就再从下一行找。这样记录哪个'#'已放棋子就更简单了，只需要记录一列上就可以了。

数据很小。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n, k, ans;
char chess[10][10];
bool take[10]; // 判断该列上是否已放棋子

void dfs(int h, int t){
    if(t == k){
        ans++;
        return ;
    }

    if(h == n) return ; // 超出最后一行要返回

    for(int i = h; i < n; i++){ // 对第h行以下的搜索
        for(int j = 0; j < n; j++){
            if(chess[i][j] == '#' && !take[j]){
                take[j] = true;
                dfs(i + 1, t + 1);
                take[j] = false; // 回溯
            }
        }
    }
}

int main()
{
    while(~scanf("%d %d", &n, &k) && n != -1 && k != -1){
        for(int i = 0; i < n; i++)
            scanf("%s", chess[i]);

        memset(take, false, sizeof(false));
        ans = 0;
        dfs(0, 0);

        printf("%d
", ans);
    }
    return 0;
}