C语言-搜索

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。

要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 k 个棋子的所有可行的摆放方案数目 C C C。

输入格式
输入含有多组测试数据。

每组数据的第一行是两个正整数 n n n, k k k，用一个空格隔开，表示了将在一个 n ∗ n n∗n n∗n 的矩阵内描述棋盘，以及摆放棋子的数目。当为 − 1 -1 −1 − 1 -1 −1时表示输入结束。

随后的 n n n 行描述了棋盘的形状：每行有 n n n 个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

输出格式
对于每一组数据，给出一行输出，输出摆放的方案数目 C C C （数据保证 C < 231 C<231 C<231）。

数据范围
n ≤ 8 n≤8 n≤8, k ≤ n k≤n k≤n

输入样例：

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

输出样例：

2
1

Code：

#include 

using namespace std;

typedef long long LL;

const int N = 10;
char map[N][N]; // 存放地图
bool col[N]; // 如果所在列有棋子为 true ，没有棋子为 false 
int n, k;
LL cnt;

void dfs(int u, int s) // 逐行枚举
{
    if(s == k) // 当放够了 k 个棋子，方案数加一后返回
    {
        cnt++;
        return;
    }
    if(u == n) return; // 越界
    
    // 不放
    dfs(u + 1, s);
    // 放
    for(int i = 0; i < n; i++) 
    {
        if(!col[i] && map[u][i] == '#')
        {
            col[i] = true; // 该列置为真，不能再放棋子
            dfs(u + 1, s + 1);
            col[i] = false; // 恢复现场
        }
    }
}

int main()
{
    while(cin >> n >> k, n != -1 && k != -1)
    {
        cnt = 0; // 注意每组数据开始前都要初始化 cnt 
        for (int i = 0; i < n; i ++) 
            for (int j = 0; j < n; j ++) cin >> map[i][j];
        dfs(0, 0);
        cout << cnt << endl;
    }
    
    return 0;
}