poj1321-棋盘问题

末蓝、 2023-07-13 15:20 5阅读 0赞

棋盘问题

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放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

#include<iostream>
    #include <algorithm>
    #include <string.h>
    using namespace std;
    int visit[20];
     char mp[20][20];
      int ans;//ans表示方案数
     int k;//k表示棋子数目
     int n;//n表示棋盘的大小
     int DFS(int x,int count)
     {
        if(count==k)//判断是否棋子已经用完，如果用完，记录方案数加1,然后直接返回0
        {
             ans++;
           return 0;
        }
         for(int i=x;i<n;i++) //可能一行没有可以放的位置 
         {
           for(int j=0;j<n;j++)
            {
                if(!visit[j]&&mp[i][j]=='#')
                 {
                     visit[j]=true;
                     DFS(i+1,count+1);//搜索下一行 
                    visit[j]=false;//回溯 
                }
            }
         }
         return 0;
     }
     int main()
     {
       while(cin>>n>>k)
        {
             if(n==-1&&k==-1)
                 break;
            memset(visit,false,sizeof(visit));
             memset(mp,false,sizeof(mp));
             for(int i=0;i<n;i++)
               cin>>mp[i];
             ans=0;
            DFS(0,0);
             cout<<ans<<endl;
         }
         return 0;
    }