搜索技术【广度优先搜索】 - 嵌套广度优先搜索 【POJ No. 1475】 推箱子 Pushing Boxes

搜索技术【广度优先搜索】 - 嵌套广度优先搜索 【POJ No. 1475】 推箱子 Pushing Boxes

在广度优先搜索里面嵌套广度优先搜索的算法被称为嵌套广度优先搜索（或称双重广度优先搜索）。

【POJ No. 1475】 推箱子 Pushing Boxes

POJ 题目地址

【题意】

想象一下，你站在一个由方格组成的二维迷宫里，这些格子可能被填满岩石，也可能没被填满岩石。

你可以一步一个格子地往北、往南、往东或往西移动。这样的动作叫作“走”。其中一个空单元格包含一个箱子，你可以站在箱子旁边，推动箱子到相邻的自由单元格。这样的动作叫作“推”。箱子除了用推的方式，不能移动，如果你把它推到角落里，就再也不能把它从角落里拿出来了。将其中一个空单元格标记为目标单元格。你的工作是通过一系列走和推把箱子带到目标格子里。由于箱子很重，所以要尽量减少推的次数。

编写程序，计算最好的移动（走和推）顺序。

【输入输出】

输入：

输入包含多个测试用例。每个测试用例的第1行都包含两个整数r 和c （均小于或等于20），表示迷宫的行数和列数。接下来是r行，每行都包含c 个字符，每个字符都描述迷宫中的一个格子，对被填满岩石的格子用“#”表示，对空格用“.”表示。对起始位置用“S”表示，对箱子的起始位置用“B”表示，对目标单元格用“T”表示。输入端以两个0终止。

输出：

对于输入中的每个迷宫，都首先输出迷宫的编号。如果无法将箱子带到目标单元格里，则输出“Impossible.”，否则输出一个最小推送次数的序列。如果有多个这样的序列，则请选择一个最小总移动（走和推）次数的序列。如果仍然有多个这样的序列，则任何一个都可被接受。将序列输出为由字符N、S、E、W、n、s、e和w组成的字符串，大写字母表示推，小写字母表示走，字母分别表示北、南、东和西这4个方向。在每个测试用例之后都输出一个空行。

【样例】

【思路分析】

问题要求先保证推箱子的次数最少，在此基础上再让人走的总步数最少。推箱子时，人只有站在箱子反方向的前一个位置，才可以将箱子推向下一个位置，如下图所示。

很明显，图中的箱子无法向上移动，因为人无法到达箱子的下面位置。因此在移动箱子时，不仅需要判断新位置有没有岩石，还需要判断人是否可以到达反方向的前一个位置，在两者均有效时，才会让人移动。

所以，先求解箱子到目标位置的最短路径（BFS1），在推箱子的过程中，每推一步，都根据推的方向和箱子的位置得到箱子的前一个位置，再求解人到达这个位置的最短路径（BFS2）。在BFS1里面嵌套了BFS2，属于嵌套广度优先搜索。

【算法设计】

① 定义一个标识数组vis[][]并将其初始化为0，标识所有位置都未被访问。

② 创建一个队列q 维护箱子的状态，将人的初始位置(sx,sy)、箱子的初始位置(bx, by)和初始路径(“”)入队，标记箱子的位置vis[bx][by]=1。

③ 如果队列不空，则队头now出队，否则返回false。

④ 从箱子的当前位置开始，向北、南、东和西这4个方向扩展。

• 得到箱子的新位置：nbx=now.bx+dir[i][0];nby=now.by+dir[i][1]。
• 得到箱子的前一个位置：tx=now.bx-dir[i][0]; ty=now.bydir[i][1]。
• 如果这两个位置有效，则执行BFS2搜索人到达箱子的前一个位置(tx, ty)的最短路径，并记录路径path。如果BFS2搜索成功，则判断是否达到目标，如果是，则返回答案ans=now.path+path+dpathB[i]；否则标记箱子的新位置被访问vis[nbx][nby]=1，将人的新位置(now.bx,now.by)、箱子的新位置(nbx,nby)和已走过的路径(now.path+path+ dpathB[i])入队。

⑤ 转向步骤3 。

【算法实现】

#include
#include
#include 
#include

using namespace std;
int N,M;
char mp[25][25];
int sx,sy,bx,by;//人和箱子的初始位置 

const int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
const char dpathB[4]={'N','S','E','W'};
const char dpathP[4]={'n','s','e','w'};

string ans;

struct person{
    int x,y;
    string path;
    person(int x_,int y_,string path_){x=x_,y=y_,path=path_;} 
};

struct node{
    int px,py,bx,by;
    string path;
	node(int px_,int py_,int bx_,int by_,string path_){
		px=px_,py=py_,bx=bx_,by=by_,path=path_;
	} 
};

bool check(int x,int y){
    if(x<0||x>=N||y<0||y>=M) return false;
    if(mp[x][y]=='#') return false;
    return true;
}

bool bfs2(int ppx,int ppy,int bbx,int bby,int tx,int ty,string &path){
	
    int vis[25][25];//局部标识数组，不要定义全局 
	memset(vis,0,sizeof(vis));//清零 
    vis[ppx][ppy]=1;//人的位置 
    vis[bbx][bby]=1;//箱子的位置
    queue<person> Q;
    Q.push(person(ppx,ppy,""));
    
    while(!Q.empty()){
        person now=Q.front();
        Q.pop();
        if(now.x==tx&&now.y==ty){//目标位置，即箱子的前一个位置 
            path=now.path;
            return true;
        }
        for(int i=0;i<4;i++){
            int npx=now.x+dir[i][0];//人的新位置 
            int npy=now.y+dir[i][1];
            if(check(npx,npy)&&!vis[npx][npy]){
                vis[npx][npy]=1;
                Q.push(person(npx,npy,now.path+dpathP[i]));
            }
        }
    }
    
    return false;
}

bool bfs(){
	
    int vis[25][25];
	memset(vis,0,sizeof(vis));//清零 
    vis[bx][by]=1;
    queue<node> q;
    q.push(node(sx,sy,bx,by,""));
    while(!q.empty()){
        node now=q.front();
        q.pop();
        
        for(int i=0;i<4;i++){
            int nbx=now.bx+dir[i][0];//箱子的新位置
            int nby=now.by+dir[i][1];
            int tx=now.bx-dir[i][0];//箱子的前一个位置 
            int ty=now.by-dir[i][1];
            string path="";
            if(check(nbx,nby)&&check(tx,ty)&&!vis[nbx][nby]){
                if(bfs2(now.px,now.py,now.bx,now.by,tx,ty,path)){
                    if(mp[nbx][nby]=='T'){
                        ans=now.path+path+dpathB[i];
                        return true;
                    }
					vis[nbx][nby]=1;
                    q.push(node(now.bx,now.by,nbx,nby,now.path+path+dpathB[i]));
                }
            }
        }
    }
    return false;
}

int main(){
	
    int cas=0;
    while(~scanf("%d%d",&N,&M),N&&M){
        for(int i=0;i<N;i++){
            scanf("%s",mp[i]);
            for(int j=0;j<M;j++){
                if(mp[i][j]=='S')
                    sx=i,sy=j;
                if(mp[i][j]=='B')
                    bx=i,by=j;
            }
        }
        printf("Maze #%d\n",++cas);
        if(bfs())
            printf("%s\n\n",ans.c_str());
        else printf("Impossible.\n\n");
    }
    
    
    return 0;
}

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
108
109
110
111
112
113
114
115
116
117
118
119
120