棋盘问题
题目描述
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
关于输入
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
关于输出
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
例子输入
2 1
#.
.#
4 4
…#
…#.
.#…
#…
-1 -1
例子输出
2
1
解题分析
这是一个典型的回溯问题，也被称为DFS（深度优先搜索）问题。我们需要在棋盘上放置k个棋子，每个棋子不能在同一行或者同一列。这个问题的解决方法是使用DFS搜索所有可能的放置方法，并在每次放置棋子时检查是否满足条件。
这段代码的主要思路如下：
-
Go函数是回溯的主体部分。它接受两个参数：当前行row和当前已放置的棋子数step。如果step大于k，说明已经找到了一种放置方法，因此增加方案数C并返回。如果row大于等于n，说明已经遍历完所有的行，因此直接返回。然后，遍历当前行的每一列，如果当前位置可以放置棋子（即board[row][j]为#），并且这一列没有放置过棋子（即col[j]为0），则在这个位置放置一个棋子，并标记这一列已经放置过棋子。然后，递归调用Go函数，进入下一行，并增加已放置的棋子数。在返回之前，取消当前位置的棋子，并标记这一列没有放置过棋子。这是回溯的关键步骤，它使得在每一行都尝试过所有可能的放置方法后，可以回到上一行并尝试其他的放置方法。 -
main函数是程序的入口点。它首先读入棋盘的大小n和要放置的棋子数k。然后，清空方案数C和列标记col。接着，读入棋盘的形状，并调用Go函数开始回溯。最后，输出方案数C。
这段代码的时间复杂性是 O(n^n)，因为在最坏的情况下，需要遍历棋盘上的每一行，并在每一行上尝试所有可能的放置方法。但是，由于棋盘的大小 n 不会超过8，因此这个时间复杂性在实际中是可以接受的。
#include <iostream>
#include <cstring>
using namespace std;
char board[9][9]; bool col[9];
int n,k; int C;
void Go(int row,int step){
if(step>k){
C++; return;
}
if(row>=n) return;
for(int j=0;j<n;j++){
if(col[j]==0 && board[row][j]=='#'){
col[j]=1;
Go(row+1,step+1);
col[j]=0;
}
}
Go(row+1,step);
}
int main() {
while(cin>>n && cin>>k){
if(n==-1 && k==-1) break;
C=0; memset(col,0,sizeof(col));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
cin>>board[i][j];
}
Go(0,1);
cout<<C<<endl;
}
return 0;
}
