POJ 1321-棋盘问题 棋盘问题 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 23209 Accepted: 11512 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 Sample Output 2 1 Source 蔡错@pku
这题可以看成是深度搜索的样题或者经典题。有点类似八皇后问题，题目要求在棋盘上能放棋子的区域放上规定数目的棋子，且保证同行和同列最多放一个棋子，问一共有多少种解法。 本题的限制条件就是同行和同列最多放一个棋子，那么我们在搜索的时候就可以以行为单位搜索，每次测试一行，这样就保证同一行最多放了一个棋子，那么怎样保证同列最多放一个棋子呢？我们可以设置一个数组`int col[]`数组，`col[i]=0`表示该行还没有放棋子；`col[i]=1`表示该行已经放了棋子了。这样我们在搜索的时候就可以这样： [cpp] if(board[i][j]==’#’&&col[j]==0)//如果可以放棋子，且这一列上还没有放过棋子 { col[j]=1;//则在该处放棋子 dfs(i,placed_num+1);//继续往下搜索 col[j]=0;//回溯 } [/cpp] 本题的思路和代码都不难，对于深度搜索的题目，还是要多做，做多了自然会摸索出其中的固定模式。下面是完整代码： [cpp] #include<iostream> using namespace std; int n,k,ans; char board[9][9];//棋盘 int col[9];//每一列是否放置了棋子，0没放；1放了。 //深度搜索，row表示上一次搜索的行号，placed_num表示已经放了几个棋子了 void dfs(int row,int placed_num) { if(placed_num==k)//如果所有棋子都放好了，则找到一个解 { ans++; return; } for(int i=row+1;i<n;i++)//否则的话，从下一行开始搜索每一行 { for(int j=0;j<n;j++)//对该行的所有位置（列） { if(board[i][j]==’#’&&col[j]==0)//如果可以放棋子，且这一列上还没有放过棋子 { col[j]=1;//则在该处放棋子 dfs(i,placed_num+1);//继续往下搜索 col[j]=0;//回溯 } } } } //初始的时候，每一列都没有放棋子 void init_col() { for(int i=0;i<9;i++) col[i]=0; } int main() { while(cin>>n>>k&&n!=-1&&k!=-1) { ans=0; init_col(); for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>board[i][j]; dfs(-1,0);//row=-1；placed_num=0 cout<<ans<<endl; } return 0; } [/cpp] 本代码AC，用时32MS，内存216K。]]>