POJ 1321 棋盘问题【DFS/回溯/放与不放/类似n皇后】

阅读量：6233 次

发布时间：2019-06-21

本文共 2240 字，大约阅读时间需要 7 分钟。

棋盘问题

Time Limit: 1000MS Memory Limit: 10000K

Total Submissions: 62164 Accepted: 29754

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

Source

蔡错@pku

【分析】：因为棋子的数量k比棋盘数目n少，那么可能有些棋盘区不用放置棋子。这是重点，易错点。

然后这道题和n皇后有点像，要求同一行、同一列不能放棋子，那么我们一行到下一行逐行搜索，是自然遍历下来的，不用管；就用一个数组标记列放没放棋子，没放过并且是棋盘区就标记可以放，然后回溯（还原现场）进行下一次尝试。

这里有两种情况，由于只要放k个棋子，且有些行不能放棋子。处理当前行的时候有两种状态，一是在当前行放棋子，二是不放棋子。放棋子就判断是否有相同列，不放棋子则直接深搜下一行。

而dfs的办法也有几种，常见的有

1.参数只有一个i表示当前搜索行；

2.参数有i表示当前搜索行和cnt表示已填充的棋子数；

3.参数有i表示当前搜索行和cnt表示已填充的棋子数，双重循环遍历，不用考虑放不放

【代码】：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,n,x) for(int i=(x); i<(n); i++)#define in freopen("in.in","r",stdin)#define out freopen("out.out","w",stdout)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                      
                        P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxn = 1e6;const int maxm = 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = {0,0,1,-1,1,-1,1,-1};const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int n,k;char a[maxm][maxm],v[maxm];int cnt,tot;void dfs(int i){ if(cnt==k) //当计数器达到k(摆放棋子的数目)，不管结果如何都结束了 { tot++; return ; } if(i>=n) return ; for(int j=0;j

转载于:https://www.cnblogs.com/Roni-i/p/9191733.html

你可能感兴趣的文章