经典的搜索类游戏

自用笔记算法

连连看 推箱子 蜘蛛纸牌

连连看

ACM-HDOJ 1175

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码（1）：深搜+剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<stdio.h>
#include <cstring>  
using namespace std;   
const int MAX = 1003;  
const int dirx[5] = {0,0,1,0,-1};
const int diry[5] = {0,1,0,-1,0};  
int map[MAX][MAX],flag[MAX][MAX];
int n,m,bx,by;  
bool mark;   
void dfs(int x,int y,int cnt,int dir)
{  
    int i,tx,ty;
    if(x<1 || y<1 || x>n || y>m || cnt>2)
		return;
    //注意下面几个剪枝的顺序，顺序搞错了就会出错，因为最后一个元素非0  
    if(x==bx && y==by)
	{ 
        mark = true;  
        return;  
    }  
    if(map[x][y]!=0)
		return;  
    if(flag[x][y]!=-1 && flag[x][y]<cnt)
		return;  
    flag[x][y] = cnt;  
    for(i=1;i<=4;i++)
	{  
        tx = x + dirx[i];  
        ty = y + diry[i];  
        if(dir!=i) 
            dfs(tx,ty,cnt+1,i);  
		else
            dfs(tx,ty,cnt,i);   
    }  
}    
int main()
{  
    int i,j,t,ax,ay;  
    while(scanf("%d %d",&n,&m)!=EOF)
	{  
        if(n==0 && m==0)
			break;  
        for(i=1;i<=n;++i) 
            for(j=1;j<=m;++j)
                scanf("%d",&map[i][j]);  
        scanf("%d",&t);  
        while(t--)
		{  
            memset(flag,-1,sizeof(flag));  
            scanf("%d %d %d %d",&ax,&ay,&bx,&by);  
            mark = false;  
            if(map[ax][ay]!=map[bx][by] || map[ax][ay]==0 || map[bx][by]==0)     //剪枝
			{  
                printf("NO\n");  
                continue;  
            }  
            flag[ax][ay] = 0;  
            for(i=1;i<=4;i++) 
                dfs(ax+dirx[i],ay+diry[i],0,i); 
            if(mark)
                printf("YES\n");  
			else
                printf("NO\n");   
        }  
    }   
    return 0;  
}

参考AC代码（2）：广搜+优化队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<stdio.h>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int S = 1010;
int n,m;
int q,sx,sy,dx,dy;
int map[S][S],flag[S][S];
const int dirx[4]={-1,1,0,0},diry[4]={0,0,-1,1};
typedef struct 
{
    int x,y,dir,turn;
}point;
queue<point>que;
inline bool check(point &P)
{
    if(P.x>=1&&P.x<=n&&P.y>=1&&P.y<=m) 
		return true;
    return false;
}
bool bfs()
{
    point cur,next;
    while(que.size())
	{
        cur = que.front();
        que.pop();
        if(cur.x==dx&&cur.y==dy) 
			return true;
        for(int i=0;i<4;i++)
		{
            if(cur.dir!=i)
			{
                next.dir=i;
                next.turn=cur.turn+1;
            }
            else
			{
                next.dir=cur.dir;
                next.turn=cur.turn;
            }
            if(next.turn>2) 
				continue;                
            next.x=cur.x+dirx[i],next.y=cur.y+diry[i];
            if(check(next)&&(!map[next.x][next.y]||(next.x==dx&&next.y==dy))&&flag[next.x][next.y]>=next.turn)
			{
                que.push(next);
                flag[next.x][next.y]=next.turn;
            }
        }
    }
    return false;
}
int main()
{
    while(scanf("%d %d",&n,&m)&&(n||m))
	{
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) 
				scanf("%d",&map[i][j]);
        scanf("%d",&q);
        while(q--)
		{
            scanf("%d %d %d %d",&sx,&sy,&dx,&dy);
            if((map[sx][sy]!=map[dx][dy])||!map[sx][sy]||!map[dx][dy]||(sx==dx&&sy==dy))
			{
                printf("NO\n");
                continue;
			}
            while(que.size()) 
				que.pop();
            memset(flag,1,sizeof(flag));
            point start;
            start.x=sx,start.y=sy,start.turn=0;
            for(int i=0;i<4;i++)
			{
                start.dir=i;
                que.push(start);
            }
            flag[sx][sy]=0;
            if(bfs()) 
				printf("YES\n");
            else 
				printf("NO\n");
        }
    }
    return 0;
}

思路

此类型为典型的搜索类题型，使用DFS或BFS均可以解决问题，再搭配优化队列或剪枝可以避免超时，超内存，减少运算复杂度。
方法一使用了深搜+剪枝：
使用数组map来储存每个位置，0代表该位置为空。数组flag作为标志数组，用来判断每个位置是否走过，用来存放到达每个点的最优化拐弯次数，并且初始化为-1。
如果进行判断的2个点不相等，或者2个点中任何一个点为空，或者2个点在同一个位置，那么直接剪枝输出NO。flag在第一个点位置的值设为0。接着开始移动起点
并进入dfs。首先如果越界或者cnt（记录转弯次数）大于2，直接剪枝，若到达终点直接返回true，如果map中该位置不为0，剪枝（空位才能走，若下一步是终点的
情况已经在上一步返回true结束循环了），若flag中存放的值不为-1（不等于-1说明该点已经走过，需要进行下一步判断）并且flag在改点的值小于cnt（flag记录
的是最优化拐弯次数，如果都小于当前可以进行的拐弯次数，那么不满足题意），剪枝。把cnt的值赋给该位置的flag。接下来继续进行移动，若dir（记录该点的方
向）和i（下一步的方向）相等，那么继续进入dfs进行下一步判断，此时代入的参数cnt不变（拐弯字数未变），i（下一步的方向）。若dir！=i，说明该点进行了拐
弯操作，那么代入的参数中cnt需要+1，继续进入dfs循环。如果第一个方向没有找到结果，那么回到主函数的for循环进行第二个方向的判断。
方法二使用了广搜+优化队列：
与方法一类似，下面只叙述不一样的部分。该方法采用了优化队列，开始是先把4个方向的结构体变量start存入队列，进入bfs进行判断，与方法一的的for循环类似，都
是可以保证在一个方向无法满足题意的情况下可以从起点开始进行下一方向的判断。接着把队列顶端的元素赋给cur，接着出队列，接着再用一个for循环进行移动，此时
判断i与que.dir是否相等，若相等则说明为拐弯，next.dir等于cur.dir，next.turn等于cur.turn，若不相等说明进行了拐弯，next.dir与目前的i保持一致，next.turn
变为cur.turn+1。接着进行一系列的判断（与方法一类似 首先保证未越界，其次地图上该点等于0可走，或者下一步已经到了终点，最后flag存放的最优化拐弯次数要大
于等于目前可以进行的拐弯次数turn）后若next满足题意，则next进队列，flag存放这一位置的最优化拐弯次数。

注意事项

由于方法略有不同，而且剪枝的顺序也不同，所以两段代码在有些方面需要注意：
第一段代码不需要判断flag存放的拐弯数是否大于2剪枝，因为在第一步的时候已经判断cnt如果大于2剪枝。并且在21行的代码中不需要判断下一个步是否到达终点。有
人可能会问，地图上除了为0的点可以走之外，如果下一步到了终点的话也是可行的，这个判断是对的，但是在前面的剪枝中已经判断如果到达了终点后直接返回true，
并不会执行下一步，换言之，如果程序执行到了第21行，那么下一步必然不可能到终点。第二段代码中也并不需要额外判断flag大于2剪枝，因为在for循环中已经判断
若turn大于2后直接continue进入下一循环。并且在这一段代码中必须判断下一步map的点为0或者是否为终点，这是由于该代码是在进行了移动后再进行判断的，没有
像第一段代码是先判断后移动，必须要注意，否则会WA。

推箱子

ACM-HDOJ 1254

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<stdio.h>
#include<iostream>  
#include<cstring>  
#include<queue>  
using namespace std;   
int Map[8][8];  
bool vis[8][8][4],us[8][8];//标记箱子推过的方向  人走过的点  
int dir[4][2]={0,1,0,-1,1,0,-1,0};  
struct node  
{  
    int x,y;  
    int xx,yy;  
    int t;  
}st,ed;  
struct edg  
{  
    int x,y;  
}a,b;  
int n,m;  
queue<node>q;   
void Bfs()  //对于箱子  广搜人能将箱子像哪个方向推  
{  
    queue<edg>qq;  
    memset(us,false ,sizeof(us));  
    qq.push(a);  
    while(qq.size())  
    {  
        a=qq.front();  
        qq.pop();  
        for(int i=0;i<4;i++)  
        {  
            int xx,yy;  
            xx=a.x+dir[i][0];  
            yy=a.y+dir[i][1];  
            if(xx>=0&&xx<n&&yy>=0&&yy<m)  
            {  
                if(xx==st.x&&yy==st.y)  
                {  
                    int x=st.x+dir[i][0],y=st.y+dir[i][1];  
                    if(x>=0&&x<n&&y>=0&&y<m)  
                    {  
                        if(!vis[x][y][i]&&Map[x][y]!=1)  //能推且到达的点不是墙  
                        {  
                            ed.x=x;  
                            ed.y=y;  
                            ed.xx=xx;  
                            ed.yy=yy;  
                            ed.t=st.t+1;  
                            q.push(ed);  
                            vis[x][y][i]=true ;  
                        }  
                    }  
                }  
                else if(!us[xx][yy]&&Map[xx][yy]!=1)  
                {  
                    us[xx][yy]=true ;  
                    b.x=xx;  
                    b.y=yy;  
                    qq.push(b);  
                }  
            }  
        }  
    }  
    return ;  
}   
void bfs()  
{  
    while(q.size()) q.pop();  
    q.push(st);  
    while(q.size())  
    {  
        st=q.front();  
        q.pop();  
        if(Map[st.x][st.y]==3)  
        {  
            printf("%d\n",st.t);  
            return ;  
        }  
        a.x=st.xx;  
        a.y=st.yy;  
        Bfs();  
    }  
    printf("-1\n");  
    return ;  
}  
int main()  
{  
    int t;  
    scanf("%d",&t);  
    while(t--&&scanf("%d%d",&n,&m))  
    {  
        for(int i=0;i<n;i++)  
        {  
            for(int j=0;j<m;j++)  
            {  
                scanf("%d",&Map[i][j]);  
                if(Map[i][j]==2)  
                    st.x=i,st.y=j;  
                if(Map[i][j]==4)  
                    st.xx=i,st.yy=j;  
            }  
        }  
        st.t=0;  
        memset(vis,false ,sizeof(vis));  
        bfs();  
    }  
}

思路

由于此题存在判断人推箱子和箱子是否到终点两个状态，所以需要使用两个广搜互相嵌套，分别用来表示箱子的状态和人推箱子的状态，配上2个优化队列，可以确保人
走的路线和箱子走的路线为最优路线，符合题目所要求的最小移动次数。在主函数中分别把箱子的起点和人的起点用st记录下来，开始的移动次数为0，接着进入第一个
dfs函数。该函数是用来判断箱子是否达到了终点。若未到达终点则把现在人的位置赋给a，接着进入二个BFS函数。该函数是用来判断人推箱子的状态。先移动人，确保
把人移到箱子的位置，若未走到箱子的位置，那么根据数组us（初始化为false）存放元素的情况和不能走到墙上继续走下一步，接着把此时人的位置赋给b，并且压入队
列qq，直到人走到目前箱子的位置，记录下元素i的值，此时的箱子只能向i方向进行移动（推箱子的游戏中箱子只能和人的运动方向一致）。箱子移动的时候需判断vis
数组中存放的元素和移动的位置是否为墙。若箱子成功走出下一步，那么把此时人和箱子的位置情况全部赋给ed，接着把ed压入队列q，接着进入第一个bfs函数判断此
时的箱子是否到达了终点，若未到达继续进入第二个BFS函数进行下一步移动。

注意事项

此题中的判断数组vis需要设置为三维数组，因为每个点都可以走1次以上，只有每个点都走过4个方向后该点才不能走。写出代码后可以用推到墙上只能顺着墙移动和推
到拐角后不能移动2个特殊情况进行验证。此题最关键的是要分清2个bfs的状态以及箱子只能和人的运动方向一致，所以先移动人后移动箱子。

蜘蛛纸牌

ACM-HDOJ 1584

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<math.h>
#include <string.h>    
int a[15],vis[15],ans;   
void dfs(int cnt,int sum)  
{  
    int i,j;  
    if(sum>=ans)  
		 return ;  
    if(cnt == 9)  
    {  
        ans = sum;  
        return ;  
    }  
    for(i = 1;i<10;i++)  
    {  
        if(!vis[i])  
        {  
            vis[i] = 1;  
            for(j = i+1;j<=10;j++)  
            {  
                if(!vis[j])  
                {  
                    dfs(cnt+1,sum+abs(a[i]-a[j]));  
                    break;  
                }  
            }  
            vis[i] = 0;  
        }  
    }  
}    
int main()  
{  
    int t,i,x;  
    scanf("%d",&t);  
    while(t--)  
    {  
        for(i = 1;i<=10;i++)  
        {  
            scanf("%d",&x);  
            a[x] = i;              //牌面为x的牌在第i个位置  
        }  
        memset(vis,0,sizeof(vis));  
        ans = 10000000;  
        dfs(0,0);  
        printf("%d\n",ans);  
    }  
    return 0;  
}

思路

使用深搜算法，判断所有的情况。首先在输入数据的时候把牌面为x的数放在数组a的第i个位置，最后使用数组a的时候就是按照从1-10的顺序来显示它们所在的位置，进
入dfs函数中后，cnt代表的是已经完成了1-9步中的第几步操作（无论如何移动，9步操作是上限），sum用来存放移动的距离。由于是遍布了所有的情况，所以每一种
情况都会对应一个sum，如果下一步的sum大于等于上一步的sum（实为第一步的sum，之后逐渐变为最小的移动数值），那么结束函数回到上一步的函数的循环中。
如果cnt已经执行了9次，而且执行到了这步说明这一步的sum小于之前的最小移动距离ans，那么把最新的sum赋给ans后结束本次函数返回上一函数的循环中。接着第
2个for循环进行遍布所有的情况。vis数组是用来判断每个位置是否使用过，未使用过为0，使用过为1。第一个for循环中如果该位置未被访问过，那么该位置赋给1后
进入第二个for循环，从i+1开始判断，if这一位置也未访问过，那么进入dfs递归，带入的参数cnt需要+1，sum为当前的sum加上2个位置差的绝对值，以此找到最小移
动距离。若未满足当前情况或已经找到目前的最短距离而退出循环后，该位置需要重新赋为0（实际运算顺序为从最后开始逆向把前面的每一个位置重新赋为0，全部赋
为0后进行新的移动和判断）。

注意事项

把牌面为x的数放在数组a的第i个位置直接简化了操作。由于数组a是按照顺序排好的，所以第二个for循环就可以直接从i+1开始判断。第二个for循环的break语句也用的
很好，因为在寻找最小距离的时候，1只能放在2上，2只能放在3上······以此类推。若1放在了3上，那么为了把2加进去，必须还要把1移走，必然不可能是最短距离了。
所以需要用break语句结束循环并把该位置的vis重新定义为0。并且第二个for循环只是找到该步的移动方向，仅此一步，下一步的移动要进行下一个dfs进行判断。第一
个for循环的i是小于10，而第二个的for循环的j为小于等于10。因为10张牌只需要进行9次操作，所以i的位置到9即可，j=i+1=10，即可进行最后一步移动。

本文标题:经典的搜索类游戏

文章作者:Hippopmonkey

发布时间:2016-08-30, 21:25:41

最后更新:2016-08-30, 21:32:40

原始链接:http://xuboming8.github.io/2016/08/30/经典的搜索类游戏/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 连连看 推箱子 蜘蛛纸牌
    1. 1.1. 连连看
      1. 1.1.1. 参考AC代码（1）：深搜+剪枝
      2. 1.1.2. 参考AC代码（2）：广搜+优化队列
      3. 1.1.3. 思路
      4. 1.1.4. 注意事项
    2. 1.2. 推箱子
      1. 1.2.1. 参考AC代码
      2. 1.2.2. 思路
      3. 1.2.3. 注意事项
    3. 1.3. 蜘蛛纸牌
      1. 1.3.1. 参考AC代码
      2. 1.3.2. 思路
      3. 1.3.3. 注意事项
|