棋盘问题

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 44012		Accepted: 21375

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

21

Source

题目链接：http://poj.org/problem?id=1321

分析：

这个题目的大意是给定一个棋盘和给定我们需要摆放的棋子的数目，然后问我们有几种摆放方式。首先我们可以明确这是一个深度搜索的题目，与八皇后问题相似。我们建立一个函数DFS用来累计可行的方案数，我们走过一列我们就把它标记下来下次的时候就不可以再摆放在这一列（因为题目要求不可以将棋子摆放在同一行和同一列）

然后就从下一行开始寻找可行的地方，直到我们摆放的棋子数与我们被要求摆放的棋子数相同时，我们就将方案数进行一次++，然后在进行递归下去。

DFS板子题，还在熟练中，争取达到闭着眼睛三分钟敲出板子！

此题我每一步给出详细解释，新手学习，大神见谅！

下面给出详解代码：

 

1 #include
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 int visit[20]; 7 char mp[20][20]; 8 int ans;//ans表示方案数 9 int k;//k表示棋子数目10 int n;//n表示棋盘的大小11 int DFS(int x,int y)12 {13     if(y>=k)//判断是否棋子已经用完，如果用完，记录方案数加1,然后直接返回014     {15         ans++;16         return 0;17     }18     for(int i=x;i
          
           >n>>k)35     {36         if(n==-1&&k==-1)37             break;38         memset(visit,false,sizeof(visit));39         memset(mp,false,sizeof(mp));40         for(int i=0;i
           
            >mp[i];42 ans=0;43 DFS(0,0);44 cout<
            
             <
            
           
          
         
        
       
      

 多年以后重写此题，想出了另外一种解决办法！

题目意思很明了，其中'#'可以放棋子，'.'不能，并且同一行或同一列不能放两个棋子，对于数据一游两种放法（'*'代表放的棋子）

*. 

#.

或

#.  

.*

对于数据二只有一种情况

...*..*..*..*...

这题只需要深搜，每次从上一个放棋子地方的下一行开始寻找可以放棋子的地方，

当发现该点时，记录行数，并更新棋盘，将于此点同行同列的都更新为'.'，

如果找不到，则返回，当把所有棋子都放上去的时候，则找到一个接，计数+1，就这样进行搜索，可以保证AC 

1 #include 
      
        2 using namespace std; 3 struct p{ 4     char s[10][10];//棋盘  5     int beforerow;//上一个棋子的行数  6 }; 7 //st表示开始搜索的棋子所在的那一行,resnum表示剩余可放的棋子数  8 int n,resnum;//n表示当前的棋盘大小为n*n,k表示可放的总棋子数 9 int ans;//摆放的所有可能数10 void DFS(p temp,int resnum)11 {12     if(resnum==0)//如果剩余棋子数量等于0,说明所有棋子都已经放好了,答案数+1返回 13     {14         ans++;15         return;16     }17     //否则就得从当前棋子的下一行开始搜索18     //并且我们知道棋子数k大于行数n的情况显然是不存在的,有了肯定是无解情况,这里就不需要讨论这个问题 19     int i,j;20     for(i=temp.beforerow+1;i<=n-resnum;i++)21     {22         for(j=0;j
       
        >n>>resnum)42     {43         44         if(n==-1&&resnum==-1)45             break;46         ans=0;47         p temp;48         temp.beforerow=-1;//此时还未放棋子,初始化为-1 49         for(int i=0;i
        
         >temp.s[i];52         }53         DFS(temp,resnum);54         cout<
         
          <