G - 迷宫问题

G - 迷宫问题

定义一个二维数组：

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<bits/stdc++.h>
using namespace std;
int n,k;
int room[5][5];
int book[5][5];
typedef struct
{
    int x;
    int y;
    int f;
}node;
node p[99];
void print(int i)
{
    if(p[i].f!=-1){
        print(p[i].f);
        cout<<"("<<p[i].x<<", "<<p[i].y<<")"<<endl;
    }
}
void bfs()
{
    int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    int head=1,tail=2,tx,ty;
    bool f=false;
    while(head<tail){
        for(int k=0;k<4;k++){
            tx=p[head].x+next[k][0];
            ty=p[head].y+next[k][1];
            if(tx<0||ty<0||ty>4||tx>4)
                continue;
            if(room[tx][ty]==0&&book[tx][ty]==0){
                book[tx][ty]=1;
                p[tail].x=tx;
                p[tail].y=ty;
                p[tail].f=head;
                tail++;
            }
            if(tx==4&&ty==4){
                f=true;
                print(head);
                break;
            }
        }
        if(f==true)
            break;
        head++;
    }
}
int main()
{
    for(int i=0;i<=4;i++)
        for(int j=0;j<=4;j++)
            cin>>room[i][j];
    memset(book,0,sizeof(book));
    book[0][0]=1;
    p[1].x=0;
    p[1].y=0;
    p[1].f=-1;
    cout<<"("<<0<<", "<<0<<")"<<endl;
    bfs();
    cout<<"("<<4<<", "<<4<<")"<<endl;
    return 0;
}