走出迷宫的最短路径

题目描述

有n*m的迷宫，该迷宫有一个入口，一个出口。编写一程序打印一条从迷宫入口到出口的最短路径，黑色方块的单元表示走不通（用1表示），白色方块的内容表示走的通（用0表示）
只能往上下左右四个方向走，如果有最短路径，保证最短路径一定是唯一的，如果没有路径可以到达，则输出“no way”。

输入

第一行输入2个整数n和m(n和m都是10~150之间的整数)，代表迷宫的行数和列数
接下来n行，每行有m个整数，1代表不可走的点，0代表可走的点
接下来一行，有2个整数s1和s2代表入口的坐标
接下来一行，有2个整数e1和e2代表出口的坐标
本题数据上保证出发点和终点的值一定为0，也就是不存在出发点和终点不能走的情况

输出

输出从入口到出口的最短路径，如果没有路径可达输出“no way”

样例输入

8 5      
1 1 1 1 1  
0 0 0 0 1
1 1 1 0 1
1 0 0 0 1
1 0 0 1 1
1 0 0 0 1
1 1 1 0 1
1 0 0 0 1
2 1  
8 4

样例输出 
(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,3)->(5,3)->(6,3)->(6,4)->(7,4)->(8,4)

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,s1,s2,e1,e2;
int q[22600][2],hh,tt,kx,ky;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int d[160][160];
int tree[22600][3],way[22600][2],minn=INT_MAX,p;
bool no=true;
bool Map[160][160];
void father(int son){
    if(son==0)
        return;
    father(tree[son][2]);
    way[p][0]=tree[son][0];
    way[p][1]=tree[son][1];
    p++;
    return;
}
void bfs(){
    if(hh==tt)
        return;
    kx=q[hh][1];
    ky=q[hh][0];
    hh++;
    for(int i=0;i<4;i++){
        int xx=kx+dx[i];
        int yy=ky+dy[i];
        if(xx>=0&&xx<m&&yy>=0&&yy<n&&!Map[yy][xx]&&d[yy][xx]==0){
            tt++;
            q[tt-1][0]=yy;
            q[tt-1][1]=xx;
            d[yy][xx]=d[ky][kx]+1;
            Map[yy][xx]==true;
            tree[tt-1][0]=ky+1;
            tree[tt-1][1]=kx+1;
            tree[tt-1][2]=hh-1;
            if(yy==e1-1&&xx==e2-1&&minn>d[yy][xx]){
                no=false;
                p=0;
                minn=d[yy][xx];
                father(tt-1);
            }
        }
    }
    bfs();
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&Map[i][j]);
    scanf("%d%d%d%d",&s1,&s2,&e1,&e2);
    if(s1==e1&&s2==e2){
        printf("(%d,%d)",e1,e2);
        return 0;
    }
    tt++;
    d[s1-1][s2-1]=1;
    q[0][0]=s1-1;
    q[0][1]=s2-1;
    bfs();
    if(no)
        printf("no way");
    else{
        for(int i=0;i<p;i++)
            printf("(%d,%d)->",way[i][0],way[i][1]);
        printf("(%d,%d)",e1,e2);
    }
    return 0;
}