#include<bits/stdc++.h>
using namespace std;
char s[605][605];
int ans=100000000,n,m,k,l,h=0,k1,l1,vis[605][605];
int dx[5]={-1,1,0,0};
int dy[5]={0,0,-1,1};
int qr_x(int x,int y,int go_x)
{
if(go_x == 0)
{
return x;
}
else
{
if(go_x == 1)
{
for(int i=x;i<=n;i++)
{
if(s[i+1][y]=='1' || i==n || (i==k1 && y==l1))
{
return i;
}
}
}
if(go_x == -1)
{
for(int i=x;i>=1;i--)
{
if(s[i-1][y]=='1' || i==1 || (i==k1 && y==l1))
{
return i;
}
}
}
}
}
int qr_y(int x,int y,int go_y)
{
if(go_y == 0)
{
return y;
}
else
{
if(go_y == 1)
{
for(int i=y;i<=m;i++)
{
if(s[x][i+1]==1 || i==m || (i==l1 && x==k1))
{
return i;
}
}
}
if(go_y == -1)
{
for(int i=y;i>=1;i--)
{
if(s[x][i-1]==1 || i==1 || (i==l1 && x==k1))
{
return i;
}
}
}
}
}
void f(int x,int y,int step)
{
if(step>=ans)
{
return ;
}
if(x==k1&&y==l1)
{
if(step>1)
{
ans=min(ans,step);
}
h=1;
return ;
}
vis[x][y]=1;
for(int i=0;i<4;i++)
{
int tx=qr_x(x,y,dx[i]);
int ty=qr_y(x,y,dy[i]);
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&s[tx][ty]!='1'&&vis[tx][ty]==0)f(tx,ty,step+1);
//cout<<ans<<endl;
}
vis[x][y]=0;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>s[i][j];
}
}
cin>>k>>l>>k1>>l1;
f(k,l,0);
if (h==1) cout<<ans;
else cout<<"No!God!Please no!";
return 0;
}
5. 暴走迷宫
题目ID：15651必做题100分
最新提交：
Wrong Answer
30 分
历史最高：
Wrong Answer
30 分
时间限制: 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,