poj 1321棋盘问题

布满荆棘的人生 2022-08-08 15:52 192阅读 0赞

递归实现深搜（Dfs）  
\[poj 1321\] ([http://poj.org/problem?id=1321][http_poj.org_problem_id_1321])  
题目描述：  
棋盘问题  
Time Limit: 1000MS Memory Limit: 10000K  
Total Submissions: 29084 Accepted: 14416  
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

言简意赅：  
此题十分类似于八皇后问题，但也不尽相同，主要是想要实现记录在一个不规则的棋盘上实现所有可能的棋子排列的方案数，难点是如何实现每一次放置棋子时都可以保证不同行并且不同列，并且将其记录下来，要借助于一遍遍历n\*n的方格，一边记录所有可能的方案数，则可借助于（递归）深搜来实现，具体代码如下：

注意：  
一旦查找到可以放置棋子的地方，就要把此棋子的同行同列的所有元素更新为’.’，依次递归下去，即可实现计数。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    int n,k;//棋盘的大致规模和要放的棋子的个数
    struct note
    {
        char map[10][10];//棋盘
        int x;//上一个棋子的行数
    };
    int ans;//用于记录所有解的个数
    
    void Dfs(note tmp,int k)
    {
        if(k==0)
        {
            ans++;//递归出口，k个棋子全部放好,则计数+1后返回
            return ;
        }
        for(int i=tmp.x+1;i<=n-k;i++)//从该行的下一个元素开始搜，若剩余行数小于要放棋子数，则无解
        {
            for(int j=0;j<n;j++)//搜索全行
            if(tmp.map[i][j]=='#')
            {
                note tmp2;//找到一个可以存放棋子的点
                tmp2=tmp;
                tmp2.x=i;
                int k1;//迭代变量
                for(k1=i+1;k1<n;k1++)
                {
                    tmp2.map[k1][j]='.';
                    //更新棋盘，由于不会再向该行和该列之前的棋盘搜索，所以只需要更新该行下同列的棋盘
                }
                Dfs(tmp2,k-1);
            }
        }
    }
    
    int main()
    {
        while(scanf("%d%d",&n,&k)!=EOF)
        {
            if(n==-1 && k==-1) break;
            ans=0;
            note map1;
            map1.x=-1;
            for(int i=0;i<n;i++)
            {
                scanf("%s",map1.map[i]);
            }
            Dfs(map1,k);
            printf("%d\n",ans);
        }
        return 0;
    }

[http_poj.org_problem_id_1321]: http://poj.org/problem?id=1321