题目1217棋盘问题题目描述在一个给定形状的棋盘形状可能是不规则的上面摆放棋子棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列请编程求解对于给定形状和大小的棋盘摆放 k 个棋子的所有可行的摆放方案 C。输入输入含有多组测试数据。每组数据的第一行是两个正整数n,k用一个空格隔开表示了将在一个n×n的矩阵内描述棋盘以及摆放棋子的数目。 (n≤8,k≤n)当为−1−1时表示输入结束。随后的n行描述了棋盘的形状每行有n个字符其中 # 表示棋盘区域. 表示空白区域数据保证不出现多余的空白行或者空白列。输出对于每一组数据给出一行输出输出摆放的方案数目C数据保证C2 31 2^{31}231。时空限制1s / 64MB样例输入2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1样例输出2 1思路和n皇后差不多但是摆放位置会小于n。可以结合n皇后的两种解法。代码#includebits/stdc.husingnamespacestd;constintN2010;intn,k,ans;boolcol[N];charg[N][N];voiddfs(intx,intsum){if(sumk){ans;return;}if(xn)return;for(inty0;yn;y)if(!col[y]g[x][y]#){col[y]true;dfs(x1,sum1);//该行放棋子col[y]false;}dfs(x1,sum);//该行不放棋子,由于可以摆放的行也可以不放棋子,所以不用else}intmain(){while(cinnk){if(n-1k-1)break;for(inti0;in;i)for(intj0;jn;j)cing[i][j];ans0;memset(col,false,sizeofcol);dfs(0,0);coutansendl;}return0;}结果