POJ 3984 迷宫问题

题目链接

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)

具体思路
裸题的bfs迷宫路径问题

#include<stdio.h>#include<queue>#include<iostream>using namespace std;typedef long long int LLD;LLD changex[5]={0,0,1,-1};LLD changey[5]={1,-1,0,0};LLD maze[5][5];LLD times[5][5];struct L{    LLD perx,pery;}way[5][5];void ans(){    LLD len=times[4][4];    LLD ansx[30],ansy[30];    LLD x=4,y=4;    ansx[len]=x;    ansy[len]=y;    len--;    while (way[x][y].perx way[x][y].pery>0)    {        ansx[len]=way[x][y].perx;        ansy[len]=way[x][y].pery;        x=ansx[len];        y=ansy[len];        len--;    }    ansx[len]=0;    ansy[len]=0;    for (LLD i=0;i<=times[4][4];i  )    {        printf("(%lld, %lld)\n",ansx[i],ansy[i]);    }    return ;}int main(){    fill(times[0],times[0] 5*5,30);    for (LLD i=0;i<5;i  )    {        for (LLD j=0;j<5;j  )        {            scanf("%lld",&maze[i][j]);        }    }    times[0][0]=0;    queue<LLD>duix;    queue<LLD>duiy;    duix.push(0);    duiy.push(0);    way[0][0].perx=0;    way[0][0].pery=0;    while (!duix.empty()&&!duiy.empty())    {        LLD x=duix.front();        LLD y=duiy.front();        duix.pop();        duiy.pop();        if (x==4&&y==4)        {            ans();            return 0;        }        for (LLD i=0;i<4;i  )        {            LLD xx=x changex[i];            LLD yy=y changey[i];            if (xx>=0&&xx<5&&yy>=0&&yy<5&&maze[xx][yy]==0&&times[xx][yy]>times[x][y] 1)            {                duix.push(xx);                duiy.push(yy);                times[xx][yy]=times[x][y] 1;                way[xx][yy].perx=x;                way[xx][yy].pery=y;            }        }    }    return 0;}

来源：https://www.icode9.com/content-4-648751.html