首页 > 代码库 > POJ 1321:棋盘问题
POJ 1321:棋盘问题
棋盘问题
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 21666 | Accepted: 10765 |
Description
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。
每组数据的第一行是两个正整数,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
2 1
深搜。注意k<n的处理。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; int n , k; int chess[10][10]; int vist[10]; int ans; void dfs(int x, int num) { if(num==k) { ans++; return ; } if(x>n) return ; for(int i=1; i<=n; i++) { if(chess[x][i]==1 && vist[i]==0) { vist[i]=1; dfs(x+1, num+1); vist[i]=0; //回溯后还原数据 } } dfs(x+1, num); } int main() { char str; while(scanf("%d%d", &n, &k)!=EOF) { memset(chess, 0, sizeof(chess)); memset(vist, 0, sizeof(vist)); ans=0; if(n==-1 && k==-1) break; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { cin>>str; if(str=='#') chess[i][j]=1; } dfs(1, 0); cout<<ans<<endl; } return 0; }
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; #define max 100 char map[max][max]; int s[max]; int n,k,i,j,a; void dfs(int x,int y) //函数参量表示的意思:x表示该棋盘的第x行,y表示放置第y个棋子 { int i,j; if(y==k) // 递归边界 a++; else { for(i=x+1;i<=n;i++) // 按行讨论 { for(j=1;j<=n;j++) // 从1 到 n列 { if( map[i][j]=='#' && !s[j] ) // 若该点是 '#'且该点的这一列没有旗子,则可以在该位置放棋子。 { s[j]=1; dfs(i,y+1); s[j]=0; } } } } } int main () { while (~scanf("%d%d",&n,&k)&&n!=-1&&k!=-1) { a=0; memset(s,0,sizeof(s)); getchar(); // for(i=1;i<=n;i++) { for(j=1;j<=n;j++) scanf("%c",&map[i][j]); getchar(); // } dfs(0,0); printf("%d\n",a); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。