题目描述

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

样例

2 1
//#.(双斜杠为了正常显示#号，下同)
.#

4 4
…#
..#.
.#..
//#…

-1 -1

2
1

算法1

这题和N皇后有点相似,但还是有不同点:
N皇后还要求对角线和辅对角线都不能放,需要使用额外数组去判断对角线和辅对角线有没有放过棋子
N皇后初始化时每个位置只有一种状态,而这题初始化时每个位置有'#'和'.',只有'#'才可以放

搜索的结束条件为：

已经放好的棋子数量等于k,方案数加一
当前行数等于n,因为从索引为0的行开始找,当前行数等于n,也就说明0~n-1行都遍历了

在dfs函数的最后面要加上 dfs(u + 1, cnt);
因为有可能在搜索某一行时,这一行的每个位置都是’.’,也有可能除了’.'外的其他位置所在的列都放了棋子,
如果没有上面这行代码,就有可能无法进到下一行去搜索

参考文献

原文链接：https://blog.csdn.net/weixin_47456072/article/details/109809864

C++ 代码

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

//n为棋盘的行数和列数,k为要放的棋子数量,ans为方案数,cnt为已经放了多少个棋子
int n, k, ans, cnt;
//存储地图
char g[10][10];
//记录某一列是否已经放了棋子
bool col[10];

void dfs(int u, int cnt) {
    //如果放了的棋子数量等于k,则添加一个方案
    if (cnt == k) {
        ans++;
        return;
    }
    //因为从索引为0的行开始找,当u等于n,也就说明0~n-1行都遍历了
    if (u == n) return;

    for (int i = 0; i < n; i++) {

        if (g[u][i] == '#' && !col[i]) {
            col[i] = true;

            dfs(u + 1, cnt + 1);

            col[i] = false; //回溯
        }
    }

    dfs(u + 1, cnt); //注意这行代码
}

int main() {
    while (cin >> n >> k) {
        if (n == -1 && k == -1) break;


        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                cin >> g[i][j];


        ans = 0, cnt = 0;
        dfs(0, 0);

        cout << ans << endl;
    }
}