poj3984迷宫问题_迷宫代码

全栈程序员-用户IM • 2022年4月21日下午4:20 • 未分类

大家好，又见面了，我是你们的朋友全栈君。

迷宫问题

定义一个二维数组：


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

Sample Output

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

本题的关键在于使用一维结构数组模拟的队列来保存符合要求的最短路径。

 1 #include <iostream>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 
 6 int maze[5][5];        //迷宫
 7 int visited[5][5];    //迷宫的访问状态
 8 int dx[4] = { 1,-1,0,0 };    //上下方向
 9 int dy[4] = { 0,0,1,-1 };    //左右方向
10 
11 struct node
12 {
13     int x, y;    //迷宫中的坐标(x,y)
14     int pre;    //(x,y)坐标的前驱
15 }q[100];    //模拟的队列
16 
17 int front = 0, rear = 1;    //front指向队首元素，rear指向队尾元素的下一个位置
18 
19 void print(int front)
20 {
21     if (q[front].pre != -1)        //这里并没有打印到起点
22     {
23         print(q[front].pre);    //使用递归进行逆序打印
24         printf("(%d, %d)\n", q[front].x, q[front].y);
25     }
26 }
27 
28 void bfs(int x, int y)
29 {
30     memset(visited, 0, sizeof(visited));    
31     visited[0][0] = 1;
32     q[0].x = x;
33     q[0].y = y;
34     q[0].pre = -1;
35 
36     while (front <= rear)    //队列不为空
37     {
38         if (q[front].x == 4 && q[front].y == 4)
39         {
40             print(front);
41             return;
42         }
43         for (int i = 0; i < 4; ++i)
44         {
45             int r = dx[i] + q[front].x;
46             int c = dy[i] + q[front].y;
47             if (r < 0 || c < 0 || r >= 5 || c >= 5 || maze[r][c] == 1 || visited[r][c])
48                 continue;
49 
50             visited[r][c] = 1;    //该点访问状态置为1
51 
52             //入队
53             q[rear].x = r;    
54             q[rear].y = c;
55             q[rear].pre = front;
56             ++rear;
57         }
58         ++front;    //队首元素出队
59     }
60     
61 }
62 
63 
64 
65 int main()
66 {
67     for (int i = 0; i < 5; ++i)
68         for (int j = 0; j < 5; ++j)
69             cin >> maze[i][j];
70 
71     cout << "(0, 0)" << endl;
72     bfs(0, 0);
73 
74 
75     return 0;
76 }