本文共 2327 字,大约阅读时间需要 7 分钟。
棋盘问题
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 60488 | Accepted: 28974 |
Description
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放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
类比八皇后,按照列放,但是区别与八皇后,这个不必每行都放,也就是可以跨行放,所以有 dfs(row+1,k)也就是对每行多出一种不放该行,直接跳到下一行的情况
刚开始,想通过在循环内对每行进行dfs依次到最后一行,但是这种思想不能涉及到,跨行的那些可能,所以错了
#include#include #include #include using namespace std;typedef long long LL;int n,k;char a[10][10];LL ans;bool vis[10];void dfs(int row,int k){ if(row > n || n-row < k) //剪枝 return ; if(k == 0){ ++ans; return; } for(int j = 0; j < n; ++j){ if(a[row][j] == '.') continue; if(!vis[j]){ vis[j] = true; dfs(row+1,k-1); vis[j] = false; } } dfs(row+1,k);}int main() { //freopen("C:Users/zhangwei/Desktop/input.txt","r",stdin); while(scanf("%d%d",&n,&k) ==2){ if(n == -1 && k == -1) break; ans = 0; for(int i = 0; i < n; ++i){ scanf("%s",a[i]); } memset(vis,false,sizeof(vis)); dfs(0,k); cout << ans << endl; } return 0; }
解法2:
#include#include #include #include
转载地址:http://drimi.baihongyu.com/