迷宫路径输出最短路径【 BFS广度优先搜索】题解

ゞ浴缸里的玫瑰 2021-07-24 15:47 393阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.代码

### 1.题目 ###

今天阿聪来到了一个滑雪胜地滑雪，但是这个时候前面出现了一座迷宫挡住了他的去路。 坚定的阿聪一定要穿过这座迷宫去滑雪！ 为了方便起见，我们定义一个二维数组来表示迷宫：

int maze\[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,

\};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出让阿聪从左上角进入迷宫到右下角离开的最短路线。

**Input**

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。  
**Output**

左上角到右下角的最短路径，格式如样例所示。

**Sample Input**  
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

**Sample Output**

(0, 0)  
(1, 0)  
(2, 0)  
(2, 1)  
(2, 2)  
(2, 3)  
(2, 4)  
(3, 4)  
(4, 4)

### 2.代码 ###

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn = 50;
    int map[5][5];
    int vis[5][5];
    int dir[4][2] = { { 0,1},{ 0,-1},{ 1,0},{ -1,0} };
    struct node
    { 
    	int x;
    	int y;
    	int pre;  //存储每个元素的下一个元素
    }q[maxn];
    int hh = 0, tt = 0; //队头和队尾 数组模拟队列
    void bfs(int bx ,int by)
    { 
    	q[0].x = bx, q[0].y = by,q[0].pre=-1;
    	tt++;
    	vis[bx][by] = 1;
    	while (hh < tt)  //队列不为空
    	{ 
    		for (int i = 0; i < 4; i++)
    		{ 
    			int nx = q[hh].x + dir[i][0];
    			int ny = q[hh].y + dir[i][1];
    			if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !vis[nx][ny] && !map[nx][ny])
    			{ 
    				q[tt].x = nx;
    				q[tt].y = ny;
    				q[tt].pre = hh;
    				tt++;
    				vis[nx][ny] = 1;
    				if (nx == 4 && ny == 4)
    				{ 
    					return;   //到达终点
    				}
    			}
    		}
    		hh++; //出队
    	}
    }
    void print(node now)  //递归输出
    { 
    	if (now.pre == -1)
    	{ 
    		cout << "(" << now.x << ", " << now.y << ")" << endl;
    	}
    	else
    	{ 
    		print(q[now.pre]);
    		cout << "(" << now.x << ", " << now.y << ")" << endl;
    	}
    }
    int main()
    { 
    	for (int i = 0; i < 5; i++)
    	{ 
    		for (int j= 0; j < 5; j++)
    		{ 
    			cin >> map[i][j];
    		}
    	}
    	bfs(0, 0);
    	print(q[tt - 1]);
    	return 0;
    }