迷宫问题

coding>C++
1.4k 词

题目描述

定义一个二维数组：

1
2
3
4
5
6
7
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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

输入

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

输出

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

样例输入

1
2
3
4
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
2
3
4
5
6
7
8
9
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

题解

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
#include<iostream>
#include <queue>

using namespace std;
const int n = 5;
int mp[n][n], v[n][n] = {0};
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
struct node {
    int x, y, prex, prey;
} st[n][n];

void bfs() {
    st[0][0].x = 0;
    st[0][0].y = 0;
    queue<node> q;
    q.push(st[0][0]);
    v[st[0][0].x][st[0][0].y] = 1;
    while (q.size()) {
        node temp = q.front();
        q.pop();
        int tx = temp.x;
        int ty = temp.y;
        if (tx == 4 && ty == 4)return;
        for (auto &i: dir) {
            int row = tx + i[0];
            int col = ty + i[1];
            if (row >= 0 && row < n && col >= 0 && col < n && mp[row][col] == 0) {
                mp[row][col] = 1;
                st[row][col].x = row;
                st[row][col].y = col;
                st[row][col].prex = tx;
                st[row][col].prey = ty;
                q.push(st[row][col]);
            }
        }
    }
}

void prt(int x, int y) {
    if (x == 0 && y == 0) {
        printf("(%d,%d)\n", st[0][0].x, st[0][0].y);
        return;
    }
    prt(st[x][y].prex, st[x][y].prey);
    printf("(%d,%d)\n", st[x][y].x, st[x][y].y);
}

int main() {
    for (auto &i: mp)
        for (int &j: i)
            cin >> j;
    bfs();
    prt(n - 1, n - 1);
    return 0;
}