POJ-3984 迷宫问题

传送门：POJ - 3984

题目描述

定义一个二维数组：

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的二维数组，表示一个迷宫。数据保证有唯一解。

输出描述

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

题意分析

bfs板子，输出的时候得注意下得回溯输出。

样例输入

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

样例输出

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

AC代码

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef map<ll, ll> mll;

#define ull unsigned long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

const int maxn=1e6+10;
const ll mod=1e9+7;
const int INF = 0x3f3f3f3f;

struct node{
    int x,y,pre;
}s,now;

int dis[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int a[10][10],vis[10][10];
int ro[10][10];

queue<node>q;

void bfs(){
    s.x=0;
    s.y=0;
    s.pre=1;
    vis[0][0]=1;
    ro[0][0]=1;
    q.push(s);
    while(!q.empty()){
        node now;
        now=q.front();
        q.pop();
        if(now.x==4&&now.y==4){
            return;
        }
        for(int i=0;i<4;i++){
            s=now;
            s.x+=dis[i][0];
            s.y+=dis[i][1];
            s.pre++;
            if(s.x<0||s.x>5||s.y<0||s.y>5||a[s.x][s.y]==1||vis[s.x][s.y]==1){
                continue;
                
            }else
            {
                vis[s.x][s.y]=1;
                q.push(s);
                ro[s.x][s.y]=s.pre;
            }
        }
    }
    
}

void print(int x,int y){
    if(x==0&&y==0)return;
    for(int i=0;i<4;i++){
        if(ro[x+dis[i][0]][y+dis[i][1]]==ro[x][y]-1){
            print(x+dis[i][0],y+dis[i][1]);
            printf("(%d, %d)\n",x,y);
        }
    }
}

int main() {
    int i,j;
    for( i=0;i<5;i++){
        for( j=0;j<5;j++){
            cin>>a[i][j];
        }
    }
    for(i=0;i<8;i++){
        for(j=0;j<8;j++){
            ro[i][i]=-5;
        }
    }
    printf("(0, 0)\n");
    bfs();
    print(4,4);
}