J - 迷宫问题

        迷宫问题,你懂的,都不用做过多的解释,直接拿着BFS就是干,不要怂。


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 <stack>
using namespace std;
class Path        //定义一个位置类
{
public:
    int x;
    int y;
    Path(int m, int n):x(m), y(n){}
};
stack<Path> mypath;
int maze[5][5], num, i, j;
void Init()        //初始化
{
    for(i=0;i<5;i++)for(j=0;j<5;j++){cin>>num;if(num)num=-1;maze[i][j]=num;}
    while(!mypath.empty())mypath.pop();
}
void Bfs(int x, int y, int flag)        //BFS搜索
{
    if(x<0||x>=5||y<0||y>=5)return;
    maze[x][y]=flag;
    for(int dx=-1;dx<=1;dx++)for(int dy=-1;dy<=1;dy++)
    {
        if((!dx || !dy) && (dx+dy) && (maze[x+dx][y+dy]==0 || maze[x+dx][y+dy]>maze[x][y]))
            Bfs(x+dx,y+dy,maze[x][y]+1);
    }
}
void PushMe(int px, int py)        //沿着目的地往回走,找最近的那条路
{
    if(px<0||px>=5||py<0||py>=5)return;
    mypath.push(Path(px, py));
    for(int dx=-1;dx<=1;dx++)for(int dy=-1;dy<=1;dy++)
    {
        if(dx+dy && (!dx&&dy || !dy&&dx) && maze[px+dx][py+dy]==maze[px][py]-1)
            PushMe(px+dx, py+dy);
    }
}
void Print()
{
    while(!mypath.empty())
    {
        cout<<"("<<mypath.top().x<<", "<<mypath.top().y<<")"<<endl;
        mypath.pop();
    }
}
int main()
{
    Init();
    Bfs(0,0,1);
    PushMe(4,4);
    Print();
}