【题解】POJ-3984 迷宫问题

发表于 分类于 ， ， ， 本文字数： 174 阅读时长 ≈ 1 分钟
POJ-3984 迷宫问题 类型 BFS 路径输出

迷宫问题 (POJ - 3984)

题面

定义一个二维数组：

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)

提示

无

思路

bfs+路径输出，记录路径有多种方式。

代码

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
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e1+5;

int b[N][N] = {{0}};
bool vis[N][N] = {{0}};
int n, m;

int dx[] = { 0,  1, -1,  0,  0};
int dy[] = { 0,  0,  0,  1, -1};

struct P {
    int x, y;
    int p[N];
    int step;
};

P bfs() {
    memset(vis, 0, sizeof(vis));

    P sp;
    sp.x = 0;
    sp.y = 0;
    sp.step = 0;
    memset(sp.p, 0, sizeof(sp.p));

    queue<P> q;
    q.push(sp);
    vis[sp.x][sp.y] = 1;

    while(!q.empty()) {
        P tp = q.front();
        q.pop();

        if(tp.x==n-1 && tp.y==m-1) {
            return tp;
        }

        P np = tp;
        for(int i=1; i<=4; i++) {
            int x = np.x = tp.x+dx[i];
            int y = np.y = tp.y+dy[i];

            if(!vis[x][y] && b[x][y]==0) {
                np.step = tp.step+1;
                np.p[np.step] = i;
                q.push(np);
                vis[x][y] = 1;
            }
        }
    }
    return sp;
}

int main(void) {
    n = m = 5;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            scanf("%d", &b[i][j]);
        }
    }
    P ans = bfs();
    if(ans.step) {
        int x=0, y=0;
        for(int i=0; i<=ans.step; i++) {
            printf("(%d, %d)\n", x+=dx[ans.p[i]], y+=dy[ans.p[i]]);
        }
    }

    return 0;
}