创意广告设计网站,郴州高椅岭,北京建设银行网站田村,海南营业执照网上怎么申请【题目描述】
在一个给定形状的棋盘#xff08;形状可能是不规则的#xff09;上面摆放棋子#xff0c;棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列#xff0c;请编程求解对于给定形状和大小的棋盘#xff0c;摆放k个棋子的所有可行的摆放方…【题目描述】
在一个给定形状的棋盘形状可能是不规则的上面摆放棋子棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列请编程求解对于给定形状和大小的棋盘摆放k个棋子的所有可行的摆放方案C。 Input 输入含有多组测试数据。 每组数据的第一行是两个正整数n k用一个空格隔开表示了将在一个n*n的矩阵内描述棋盘以及摆放棋子的数目。 n 8 , k n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状每行有n个字符其中 # 表示棋盘区域 . 表示空白区域数据保证不出现多余的空白行或者空白列。 Output 对于每一组数据给出一行输出输出摆放的方案数目C 数据保证C2^31。 Sample Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1Sample Output
2
1【题目分析】这是一道很简单的DFS但是在做的时候因为不小心加上了cin的优化
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);导致一直wa还有就是对于状态的记录以及设置的参数一定要起到作用 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;int n,k,ans,t;
char a[10][10];
bool y[10];void dfs(int u)
{if(tk){ans;return;}if(un) return;for(int j0;jn;j){if(!y[j] a[u][j]#){y[j]true;t;dfs(u1);y[j]false;t--;}}dfs(u1);
}int main()
{while(cinnk){if(n-1 k-1)break;memset(a,0,sizeof(a));//memset(x,0,sizeof(x));memset(y,0,sizeof(y));ans0; t0;for(int i0;in;i){scanf(%s,a[i]);}dfs(0);printf(%d\n,ans);}return 0;}
