20.02.28走迷宫

02.28 王琼老师第一次通过二叉树的遍历给大家引荐了深度优先搜索。
6行8列的迷宫，计算从(0,0)到(5,7)的路径
0 0 1 0 0 0 0 0
1 0 1 0 1 1 1 1
1 0 0 0 0 0 0 1
1 0 1 1 0 1 0 1
1 0 1 1 0 1 1 1
1 0 0 0 0 0 0 0
请各位同学编程，实现最短路径并打印

#include<cstdio>    
#include<cstdlib>        
#include<iostream>
#include<algorithm>
#include <iostream>
using namespace std;
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<cmath> 
#include<queue>
#define EPS 1e-6
#define MAX 1010
int ans,mp[MAX][MAX],vis[MAX][MAX],xi[MAX],yi[MAX],cnt=0;
const int dx[]={0,0,-1,1};
const int dy[]={1,-1,0,0};
struct node{
    int x,y,step;
};
node pre[MAX][MAX];
bool check(int px,int py){
    if(px<0||py<0||px>=6||py>=8||mp[px][py]==1) return  false;
    return true;
}
void init(){
    ans=0;
    memset(vis,0,sizeof(vis));
}
void bfs(int px,int py){
    queue <node> Q;
    Q.push(node{px,py,0});
    vis[px][py]=1;
    while(!Q.empty()){
        node t=Q.front();
        Q.pop();
        if(t.x==5&&t.y==7){
            ans=t.step;
            break;
        }
        for(int i=0;i<4;i++){
            int nx=t.x+dx[i];
            int ny=t.y+dy[i];
            if(check(nx,ny)&&!vis[nx][ny]){
                Q.push(node{nx,ny,t.step+1});
                vis[nx][ny]=1;
                pre[nx][ny]=t;
            }
        }
    }
}
void print(node cur){
    if(cur.x==0&&cur.y==0){
        cout<<"(0, 0)"<<endl;
        return;
    }
    print(pre[cur.x][cur.y]);
    cout<<"("<<cur.x<<", "<<cur.y<<")"<<endl;
}
int main(){
    cout<<"迷宫:"<<endl; 
    for(int i=0;i<6;i++){
        for(int j=0;j<8;j++){
            cin>>mp[i][j];
        }
    }
    bfs(0,0);
    cout<<"最短路径如下："<<endl; 
    print(node{5,7,ans});
    cout<<"最短路径步数:"<<endl; 
    cout<<ans<<"步";
    return 0;
}