在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1#..#4 4...#..#..#..#...-1 -1
Sample Output
21 好久没更新题目了，没认真刷过题了，今天一个水题都写了这么久 类似八皇后的模板题、 贴一份开始自己想的代码，时间复杂度又长又水 定义了两个vis数组，想着只要开始让第一个数组补课访问就行，没有考虑清楚回溯，在回溯的时候因为你的cnt没变，一直增加，可能通过其他前面已经访问过的点增加cnt值，造成错误
#include#include #include #include #include #define ls (u<<1)#define rs (u<<1|1)#define maxn 1010#define ll long long#define INF 1e9using namespace std;#define max(a,b) (a)>(b)?(a):(b)#define min(a,b) (a)<(b)?(a):(b)int n,k,vis1[10][10],vis2[10][10],step;char mapn[10][10];void dfs(int cnt){ if(cnt == k){ step ++; return; } if(cnt == 1){ memset(vis2,0,sizeof(vis2)); } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(mapn[i][j] == '#' && !vis1[i][j] && !vis2[i][j]){ vis2[i][j] = 1; dfs(cnt + 1); } } }}int main(){ while(cin >> n >> k){ if(n == -1 && k == -1){ break; } step = 0; memset(vis1,0,sizeof(vis1)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin >> mapn[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(mapn[i][j] == '#'){ vis1[i][j] = 1; dfs(1); } } } cout << step << endl; } return 0;}
注意这种写法，可以节省时间，直接以行dfs，然后一个循环竖行的值，找到一行中的值时又重新进入下一行
注意 同一行或同一列不能有其他棋子！！！连题目都没看清，果然水了很多
#include#include #include #include #include #define ls (u<<1)#define rs (u<<1|1)#define maxn 1010#define ll long long#define INF 1e9using namespace std;#define max(a,b) (a)>(b)?(a):(b)#define min(a,b) (a)<(b)?(a):(b)int n,k,vis[10],step,sum;char mapn[10][10];void dfs(int cnt){ if(sum == k){ step ++; return; } if(cnt > n){ return; } for(int i=1;i<=n;i++){ if(mapn[cnt][i] == '#' && !vis[i]){ vis[i] = 1; sum ++; dfs(cnt + 1); sum --; vis[i] = 0; } } dfs(cnt + 1);}int main(){ while(cin >> n >> k){ if(n == -1 && k == -1){ break; } step = 0; sum = 0; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin >> mapn[i][j]; } } dfs(1); cout << step << endl; } return 0;}