12. 暴走迷宫
XJOI - 题目ID：15651选做题100分
最新提交：
Time Limit Exceeded
70 分
历史最高：
Time Limit Exceeded
70 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
鱼大大又又又一(chun)不(shu)小(gu)心(yi)掉进了一个迷宫，好在外援羊大大很快为鱼大大弄到了迷宫的地图，并指挥鱼大大如何走出迷宫。
不过这回的迷宫有亿点点区别，这个迷宫的地面是冰面！鱼大大只要往前走一步，那是吃了炫迈一样，那是根本停不下来呀，直到有墙壁拦住了他的脸(被墙挡在前一格子)或是直接从出口滑出迷宫。
就这样鱼大大走一步滑一段，问鱼大大最少几步即可能走出这个迷宫呢？
【输入格式】
第一行两个整数 n, m;表示迷宫的行列。
接下来n行，每行m个数字，0/1分别表示路和墙。
最后一行4个整数x1,y1,x2,y2,表示鱼大大掉入迷宫的位置和迷宫出口的位置。
【输出格式】
一个整数表示鱼大大需要走的最少步数
注：如果走不出来，输出“No!God!Please no!”
【样例输入】
3 8
01000000
00100000
00001000
1 1 1 6
【样例输出】
4
样例说明：
鱼大大从(1,1)开始，往下走第1步，滑到(3,1)，再向右走第2步，滑到(3,4)遇到墙停下，再向上走第3步，滑到(1,4)，再向右走第4步，滑到出口
【数据范围】
对于30%的数据：每次只往前走一格必遇到墙壁
对于70%的数据：每次最多走两格必遇到墙壁
对于100%的数据：2≤n,m≤500,
我的代码：
#include<queue>
#include<iostream>
using namespace std;
int n,m;
char a[505][505];
int dx[]={-1,0,0,1};
int dy[]={0,-1,1,0};
int sx,sy,ex,ey;
struct node{
int x,y,step;
};
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
cin>>sx>>sy>>ex>>ey;
queue<node>q;
q.push(node{sx,sy,0});
while(!q.empty()){
int x=q.front().x,y=q.front().y,s=q.front().step;
q.pop();
if(x==ex&&y==ey){
cout<<s;
return 0;
}
for(int i=0;i<4;i++){
int tx=x,ty=y;
while(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]=='0'){
if(tx==ex&&ty==ey){
cout<<s+1;
return 0;
}
tx+=dx[i];
ty+=dy[i];
}
tx-=dx[i];
ty-=dy[i];
if(tx==ex&&ty==ey){
cout<<s+1;
return 0;
}
if(tx==x&&ty==y) continue;
q.push(node{tx,ty,s+1});
}
}
cout<<"No!God!Please no!";
return 0;
}