POJ3984——迷宫问题

Problem

定义一个二维数组：
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)

---

思路

迷宫最短路模板题，借助queue，BFS即可，用stack辅助记录路径。

代码

#include<iostream>
#include<queue>
#include<stack>
using namespace std;
int maze[5][5],vis[5][5]={0},dist[5][5];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
struct Node {
    int x,y;
    Node(int x,int y):x(x),y(y){}
    Node(){}
}pre[5][5];
queue<Node> Q;

void BFS() {
    while(!Q.empty()) Q.pop();
    dist[0][0]=0;
    vis[0][0]=1;
    Q.push(Node(0,0));
    while(!Q.empty())  {
        Node node=Q.front();Q.pop();
        int x=node.x,y=node.y;
        for(int d=0;d<4;d++)  {
            int nx=x+dx[d];
            int ny=y+dy[d];
            if(nx>=0&&nx<5&&ny>=0&&ny<5&&vis[nx][ny]==0&&maze[nx][ny]==0)  {
                vis[nx][ny]=1;
                Q.push(Node(nx,ny));
                dist[nx][ny]=1+dist[x][y];
                pre[nx][ny]=Node(x,y);
                if(nx==4&&ny==4) return;
            }
        }
    }
}

int main()  {
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            cin>>maze[i][j];
    BFS();
    stack<Node> S;
    int cur_x=4,cur_y=4;
    while(1){
        S.push(Node(cur_x,cur_y));
        if(cur_x==0&&cur_y==0) break;
        int x=cur_x,y=cur_y;
        cur_x=pre[x][y].x;
        cur_y=pre[x][y].y;
    }
    while(!S.empty()){
        Node node=S.top();
        cout<<'('<<node.x<<", "<<node.y<<')'<<endl;
        S.pop();
    }
    return 0;
}