1255：迷宫问题

传送门：http://ybt.ssoier.cn:8088/problem_show.php?pid=1255

 

【题目描述】

定义一个二维数组：

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

【输出】

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

【输入样例】

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)

#include<iostream>
#include<queue>
#include<cstring>
using namespace std; 
#define N 100+1
struct node{
    int x,y;
};
int map[10][10],n;
bool maps[10][10];
int xs[]={1,-1,0,0};
int ys[]={0,0,-1,1};
node jb[6][6];
void print(int x,int y)
{
    if(x==1&&y==1)cout<<"("<<x-1<<", "<<y-1<<")"<<endl;
    else 
    {
        print(jb[x][y].x,jb[x][y].y);
        cout<<"("<<x-1<<", "<<y-1<<")"<<endl;
    }
    return;
}
void bfs()
{
    queue <node> q;
    node t;
    t.x=1;t.y=1;
    q.push(t);
    while(!q.empty())
    {
        node c=q.front();q.pop();
        if(c.x==5&&c.y==5)
        {
            print(5,5);
            break;
        }
        for(int i=0;i<4;i++)
        {
            int x=c.x+xs[i];
            int y=c.y+ys[i];
            if(maps[x][y]==true&&x>=1&&x<=5&&y>=1&&y<=5)
            {
                maps[x][y]=false;
                node tmp;
                tmp.x=x;
                tmp.y=y;
                q.push(tmp);
                jb[x][y].x=c.x;
                jb[x][y].y=c.y;
            }
        }
    }
    return;
}
int main()
{
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            cin>>map[i][j];
    memset(maps,false,sizeof(maps));
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            if(map[i][j]==0)
                maps[i][j]=true;
    bfs();
}