专栏首页小樱的经验随笔POJ 1321 棋盘问题(DFS板子题,简单搜索练习)

POJ 1321 棋盘问题(DFS板子题,简单搜索练习)

棋盘问题

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

2
1

Source

蔡错@pku

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

分析:

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

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

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

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

下面给出详解代码:

 1 #include<iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 #include <string.h>
 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,然后直接返回0
14     {
15         ans++;
16         return 0;
17     }
18     for(int i=x;i<n;i++)
19     {
20         for(int j=0;j<n;j++)
21         {
22             if(!visit[j]&&mp[i][j]=='#')//标记数组仅仅标记某一列上是否有棋子,因为每次递归下一列,所以每一列不会有冲突,只需判断这一列上是否有其他棋子
23             {
24                 visit[j]=true;//如果该位置该列没被标记且为棋盘,那么在这里放上棋子,并标记,
25                 DFS(i+1,y+1);//搜索下一列
26                 visit[j]=false;//还要注意修改标记后递归回来要及时复原
27             }
28         }
29     }
30     return 0;
31 }
32 int main()
33 {
34     while(cin>>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<n;i++)
41             cin>>mp[i];
42         ans=0;
43         DFS(0,0);
44         cout<<ans<<endl;
45     }
46     return 0;
47 }

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

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

*. 

#.

#.  

.*

对于数据二只有一种情况

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

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

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

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

 1 #include <iostream>
 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;j++)
23         {
24             if(temp.s[i][j]=='#')
25             {
26                 p temp1;
27                 temp1=temp;
28                 temp1.beforerow=i;//记下改点的行数 
29                 int k;
30                 for(k=i+1;k<n;k++)//更新棋盘 
31                 {
32                     temp1.s[k][j]='.';
33                 }
34                 DFS(temp1,resnum-1);//放好一个棋子继续搜 
35             }
36         }
37     } 
38 }
39 int main()
40 {
41     while(cin>>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<n;i++)
50         {
51             cin>>temp.s[i];
52         }
53         DFS(temp,resnum);
54         cout<<ans<<endl;
55     }
56     return 0;
57 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 详解斯坦纳点及斯坦纳树及模版归纳总结

    ①什么是斯坦纳点?   假设原来已经给定了个点,库朗等指出需要引进的点数至多为,此种点称为斯坦纳点。过每一斯坦纳点,至多有三条边通过。若为三条边,则它们两两交成...

    Angel_Kitty
  • UESTC 1599 wtmsb【优先队列+排序】

    题目链接:UESTC 1599 wtmsb 题意:给你一组数,每一次取出两个最小的数,将这两个数的和放入这组数中,直到这组数只剩下一个,求最后剩下那个数的大小!...

    Angel_Kitty
  • BZOJ 1800: [Ahoi2009]fly 飞行棋【思维题,n^4大暴力】

    1800: [Ahoi2009]fly 飞行棋 Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 1689  So...

    Angel_Kitty
  • 数据结构回顾及展望(二)(3.22更新)

    事在人为,盛衰之理,虽曰天命,岂非人事哉!原庄宗之所以得天下,与其所以失之者,可以知之矣。------------《伶官传序》

    glm233
  • View的绘制流程之MeasureSpec

    目的 我在一个多月之前就说我准备开始梳理基础的事,好吧,我承认这一个月没我怎么梳理。或者梳理的不多,当我梳理到view的时候,发现需要分成绘制流程以及事件分发进...

    我就是马云飞
  • 洛谷P4015 运输问题(费用流)

    题目描述 WW 公司有 mm 个仓库和 nn 个零售商店。第 ii 个仓库有 a_iai​ 个单位的货物;第 jj 个零售商店需要 b_jbj​ 个单位的货物。...

    attack
  • LWC 59:730. Count Different Palindromic Subsequences

    LWC 59:730. Count Different Palindromic Subsequences 传送门:730. Count Different Pa...

    用户1147447
  • 蓝桥杯 基础练习 数列排序

    第一行为一个整数n。 第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。

    Debug客栈
  • 详解斯坦纳点及斯坦纳树及模版归纳总结

    ①什么是斯坦纳点?   假设原来已经给定了个点,库朗等指出需要引进的点数至多为,此种点称为斯坦纳点。过每一斯坦纳点,至多有三条边通过。若为三条边,则它们两两交成...

    Angel_Kitty
  • 寻找大富翁

    题目描述 浙江桐乡乌镇共有n个人,请找出该镇上的前m个大富翁. 输入描述: 输入包含多组测试用例. 每个用例首先包含2个...

    AI那点小事

扫码关注云+社区

领取腾讯云代金券