BFS之迷宫问题-输出路径

灰太狼 2021-09-21 08:54 355阅读 0赞

### 迷宫问题 ###

*   *  引言
     *   *  例题一(打印坐标)
         *  例题二(打印方向)

## 引言 ##

广度优先搜索（BFS）可以很方便的去解决迷宫问题。根据广度优先搜索的特点，利用BFS得到的路径就是最短的路径。对于简单的问**最短路径长度的问题**。我们可以通过在表示位置的结构体中加上一个step变量，在BFS的时候逐步更新step。当到达终点的时候返回最终的step即可。

而对于要打印路径问题，就需要**额外的开一个数组来存放当前结点的前驱结点的信息。**  
通过两个例子来说明一下：

### 例题一(打印坐标) ###

> 用一个二维数组表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。**数据保证有唯一解**  
> 输入：（一个5\*5的数组）  
> 0 1 0 0 0  
> 0 1 0 1 0  
> 0 0 0 0 0  
> 0 1 1 1 0  
> 0 0 0 1 0  
> 输出：  
> (0, 0)  
> (1, 0)  
> (2, 0)  
> (2, 1)  
> (2, 2)  
> (2, 3)  
> (2, 4)  
> (3, 4)  
> (4, 4)

我们开一个结构体数组来保存当前结点的前驱结点 `node pre[maxn][maxn]` 。这样在每次BFS操作的时候，对于满足条件的结点，将其前驱结点保存在`pre[nowX][nowY]`中。最后通过DFS递归搜索一下就可以得到答案。需要特别注意的是：这道题说了答案唯一，那么我们在探索当前结点的四个方向的可达性的时候就可以不用在意次序的问题。给出示例代码：

#include<cstdio>
    #include<queue>
    using namespace std;
    const int n=6;
    int Maze[n][n];//代表迷宫
    bool vis[n][n];//是否已经入队 
    struct node{  
    	int x, y;
    }temp;
    node pre[n][n]; //记录每个节点
    int X[] = { 0,0,-1,1};
    int Y[] = { -1,1,0,0};
    
    bool judge(int x, int y){ 
    	if(x < 0 || x>4 || y<0 || y>4)return false;
    	if(Maze[x][y] == 1) return false;
    	if(vis[x][y] == true) return false;
    	return true;
    } 
    
    void BFS(node s){ 
    	queue<node>q;
    	q.push(s);
    	vis[s.x][s.y] = true;
    	while(!q.empty()){ 
    		node t = q.front();
    		q.pop();
    		for(int i=0; i<4; i++){ 
    			int newX = t.x + X[i];
    			int newY = t.y + Y[i];
    			if(judge(newX,newY)){ 
    				pre[newX][newY] = t;
    				temp.x = newX;
    				temp.y = newY;
    				q.push(temp);
    				vis[newX][newY] = true;	
    			}
    		}
    		
    	}
    }
    
    void DFS(int x, int y){ 
    	if(x ==0 && y==0){ 
    		printf("(%d, %d)\n",x,y);
    		return;
    	}
    	temp = pre[x][y];
    	DFS(temp.x,temp.y);
    	printf("(%d, %d)\n",x,y);
    }
    
    
    int main(){ 
    	for(int i=0; i<5; i++){ 
    		for(int j=0; j<5; j++){ 
    			scanf("%d",&Maze[i][j]);
    		}
    	}
    	temp.x = temp.y = 0;
    	BFS(temp);
    	DFS(4,4);
    	return 0;
    }

### 例题二(打印方向) ###

在来看一道要关注次序的问题：

> 下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可 以通行的地方。迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。
> 
> 010000  
> 000100  
> 001001  
> 110000  
> 请找出一种通过迷宫的方式， **其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案**。例如这个例子的输出: DRRURRDDDR  
> 请注意在字典序中D<L<R<U。

这个时候就需要关注遍历次序了，也就是在构造X数组和Y数组的时候，要按照下，左，右，上的顺序来遍历，这样字典序最小的的序列会最先被找到，然后结束BFS。这道题自己是在上一道打印坐标的基础上改了一下，将坐标信息先存入了vector中，然后遍历容器输出相应的顺序。参考代码如下：

#include<cstdio>
    #include<queue>
    #include<algorithm>
    #include<vector>
    #include<string>
    #include<iostream>
    using namespace std;
    const int maxn = 60;
    int n,m;
    bool vis[maxn][maxn];
    int X[]={ 1,0,0,-1}; //这两个数组中元素的位置是固定的，不能乱放 
    int Y[]={ 0,-1,1,0};
    int Maze[maxn][maxn];
    string strs[maxn];
    struct node{ 
    	int x,y;
    }Node;
    node pre[maxn][maxn];//记录前驱结点 
    vector<node>vec; //方便最后输出 
    
    bool judge(int x, int y){ 
    	if(x<0 || x>=n || y<0 || y>=m)return false;
    	if(vis[x][y]==true)return false;
    	if(Maze[x][y]==1)return false; 
    	return true;
    }
    
    void BFS(node s){ 
    	queue<node>q;
    	q.push(s);
    	vis[s.x][s.y]=true;
    	while(!q.empty()){ 
    		node top = q.front();
    		q.pop();
    		for(int i=0; i<4; i++){ 
    			int newX = top.x + X[i];
    			int newY = top.y + Y[i];
    			if(judge(newX,newY)){ 
    				vis[newX][newY]=true;
    				Node.x = newX;
    				Node.y = newY;
    				pre[newX][newY]=top; //记录前驱结点 
    				q.push(Node);
    			}
    			if(newX == n-1 && newY == m-1){ 
    				break;
    			}
    		}
    		
    	}
    	
    }
    //将坐标信息从按从起点到终点存入vector中 
    void DFS(int x,int y){ 
    	if(x == 0 && y == 0){ 
    		Node.x = x,Node.y=y;
    		vec.push_back(Node);
    		return ;
    	}
    	DFS(pre[x][y].x,pre[x][y].y);
    	Node.x = x,Node.y=y;
    	vec.push_back(Node);
    }
    //根据相邻坐标的位置信息打印如何走 
    void print(){ 
    	for(int i=0; i<vec.size()-1; i++){ 
    		node next = vec[i+1];
    		node now = vec[i];
    		if(next.x > now.x)printf("D");
    		else if(next.x < now.x)printf("U");
    		else if(next.y > now.y)printf("R");
    		else printf("L");
    	}	
    }
    int main(){ 
    	scanf("%d%d",&n,&m);
    	getchar();
    	for(int i=0; i<n; i++){ 
    		getline(cin,strs[i]);
    	}
    	for(int i=0; i<n; i++){ 
    		for(int j=0; j<m; j++){ 
    			Maze[i][j] = strs[i][j]-'0';
    		}
    	}
    	node start,end;
    	start.x = 0,start.y = 0;
    	BFS(start);
    	DFS(n-1,m-1);
    	print();
    	return 0;
    	
    }

测试结果：

> 010000  
> 000100  
> 001001  
> 110000

![在这里插入图片描述][20200630213303146.JPG]

> 01010101001011001001010110010110100100001000101010  
> 00001000100000101010010000100000001001100110100101  
> 01111011010010001000001101001011100011000000010000  
> 01000000001010100011010000101000001010101011001011  
> 00011111000000101000010010100010100000101100000000  
> 11001000110101000010101100011010011010101011110111  
> 00011011010101001001001010000001000101001110000000  
> 10100000101000100110101010111110011000010000111010  
> 00111000001010100001100010000001000101001100001001  
> 11000110100001110010001001010101010101010001101000  
> 00010000100100000101001010101110100010101010000101  
> 11100100101001001000010000010101010100100100010100  
> 00000010000000101011001111010001100000101010100011  
> 10101010011100001000011000010110011110110100001000  
> 10101010100001101010100101000010100000111011101001  
> 10000000101100010000101100101101001011100000000100  
> 10101001000000010100100001000100000100011110101001  
> 00101001010101101001010100011010101101110000110101  
> 11001010000100001100000010100101000001000111000010  
> 00001000110000110101101000000100101001001000011101  
> 10100101000101000000001110110010110101101010100001  
> 00101000010000110101010000100010001001000100010101  
> 10100001000110010001000010101001010101011111010010  
> 00000100101000000110010100101001000001000000000010  
> 11010000001001110111001001000011101001011011101000  
> 00000110100010001000100000001000011101000000110011  
> 10101000101000100010001111100010101001010000001000  
> 10000010100101001010110000000100101010001011101000  
> 00111100001000010000000110111000000001000000001011  
> 10000001100111010111010001000110111010101101111000

输出：

> DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

[20200630213303146.JPG]: /images/20210920/6c0e97a0c0324f3eba163ff73ad00328.png