poj 3984 迷宫问题打印路径模板

快来打我* 2022-05-31 12:30 162阅读 0赞

迷宫问题

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>28201</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;16264</td> 
  </tr> 
 </tbody> 
</table>

Description

定义一个二维数组：

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)

代码：

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <stack>
    #include <queue>
    using namespace std;
    const int maxn = 5;
    int sx,sy;
    bool vis[maxn][maxn];
    int dir[4][2] = {0,1,0,-1,1,0,-1,0};
    int mapp[maxn][maxn];
    int ans = 0;
    struct Pos
    {
        Pos(int x,int y)
        {
            this->x =x;
            this->y = y;
        }
        int x;
        int y;
    };
    stack<Pos>path;
    stack<Pos>path1;
    struct node
    {
        int x,y;
        node(int a,int b):x(a),y(b) {}
    };
    struct road
    {
        int x,y,step;
        vector<node>v;
    };
    
    int check(int x,int y)
    {
        if(x<0||x>4||y<0||y>4)
            return 1;
        if(vis[x][y] || mapp[x][y]==1)
            return 1;
        return 0;
    }
    
    queue<node>q1;
    queue<node>q2;
    void bfs()
    {
        road a,next;
        queue<road>Q;
        a.x = 0;
        a.y = 0;
        a.step = 0;
        Q.push(a);
        vis[a.x][a.y]=true;
        a.v.push_back(node(0,0));
        while(!Q.empty())
        {
            a = Q.front();
            Q.pop();
            if(a.x==4&&a.y==4)
            {
                ans = a.step;
                for(int i=0; i<a.v.size(); i++)
                {
                    path.push(Pos(a.v[i].x,a.v[i].y));
                }
                return;
            }
            for(int i=0; i<4; i++)
            {
                next = a;
                next.x += dir[i][0];
                next.y += dir[i][1];
                if(check(next.x,next.y))
                    continue;
                next.step = a.step+1;
                vis[next.x][next.y] = 1;
                next.v.push_back(node(next.x,next.y));
               // q1.push(next);
                Q.push(next);
            }
        }
    }
    int main()
    {
        //freopen("in.txt","r",stdin);
        for(int i=0; i<maxn; i++)
            for(int j=0; j<maxn; j++)
                cin>>mapp[i][j];
        memset(vis,false,sizeof(vis));
        bfs();
        while (!path.empty())
        {
            Pos pos = path.top();
            path1.push(pos);
            path.pop();
        }
        cout<<"(0, 0)"<<endl;
        while(!path1.empty())
        {
            Pos pos = path1.top();
            cout<<"("<<pos.x<<", "<<pos.y<<")"<<endl;
            path1.pop();
        }
    
        return 0;
    }