首页 > 代码库 > poj-1321
poj-1321
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
解题思路:
该题需要用到回溯法,搜索的时候用逐行深搜,其实跟八皇后为题类似,题目中也给出(数据保证不出现多余的空白行或者空白列),所以逐行深搜判断列有无重复即可。
难点是在每一行有两种情况,一是放棋子,这时候需要回溯,因为一行可能出现多个位置可以放。二是不放棋子,因为可能棋子数会比位置少,所以不放棋子的时候可以直
接递归。
具体代码:
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 char map[9][9]; 5 bool lie[9]; 6 int n,k,te,sta; 7 void dfs(int x,int num) 8 { 9 if(num==k) 10 { 11 sta++; 12 return; 13 } 14 if(x>n) 15 return; 16 for(int j=1;j<=n;j++) 17 { 18 if(map[x][j]==‘#‘&&!lie[j]) 19 { 20 lie[j]=true; 21 dfs(x+1,num+1); 22 lie[j]=false; 23 } 24 } 25 dfs(x+1,num); 26 } 27 int main() 28 { 29 while(cin>>n>>k) 30 { 31 te=k; 32 memset(lie,0,sizeof(lie)); 33 if(n==-1&&k==-1) 34 break; 35 sta=0; 36 for(int i=1;i<=n;i++) 37 for(int j=1;j<=n;j++) 38 cin>>map[i][j]; 39 dfs(1,0); 40 cout<<sta<<endl; 41 } 42 //system("pause"); 43 return 0; 44 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。