【POJ No. 3984】 迷宫问题

【POJ No. 3984】 迷宫问题

POJ 题目地址

【题意】

用一个二维数组表示一个迷宫，其中1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，

编写程序，找出从左上角到右下角的最短路线。

【输入输出】

输入：

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

输出：

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

【样例】

【思路分析】

本题为典型的迷宫问题，可以使用广度优先搜索解决。定义方向数组dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}}，定义前驱数组pre[][]记录经过的节点。

【算法设计】

① 定义一个队列，将起点(0, 0)入队，标记已走过。

② 如果队列不空，则队头出队。

③ 如果队头正好是目标(4, 4)，则退出。

④ 沿着4个方向搜索，如果该节点未出边界、未走过且不是墙壁，则标记走过并入队，用前驱数组记录该节点。

⑤ 转向步骤2。

⑥ 根据前驱数组输出从起点到终点的最短路径。

【算法实现】

#include
#include

using namespace std;

int mp[5][5],vis[5][5];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

struct node{
    int x,y;
};

node pre[10][10];

void bfs(){
	
    queue<node> que;
    node st;
    st.x=st.y=0;
    que.push(st);
    vis[0][0]=1;
    
    while(!que.empty()){
    	
        node now=que.front();
        que.pop();
        
        if(now.x==4&&now.y==4)
            return;
        for(int i=0;i<4;i++){
        	
            node next;
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            if(next.x>=0&&next.x<5&&next.y>=0&&next.y<5&&!mp[next.x][next.y]&&!vis[next.x][next.y]){
                vis[next.x][next.y]=1;
                que.push(next);
                pre[next.x][next.y]=now;
            }
        }
    }
}

void print(node cur){
	
    if(cur.x==0&&cur.y==0){
        printf("(0, 0)\n");
        return;
    }
    
    print(pre[cur.x][cur.y]);//逆序输出
    printf("(%d, %d)\n",cur.x,cur.y);
}

int main(){
	
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            scanf("%d",&mp[i][j]);
    bfs();
    
    node ed;
    ed.x=ed.y=4;
    print(ed);
    
    return 0;
}

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