houluyu @ 2022-10-10 19:09:02
只有60分
#include<iostream>
#include<cstdio>
using namespace std;
int n,stx,sty,enx,eny;
bool map_[10005][10005];
bool used[10005][10005];
long long x[400005],y[400005],z[400005];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
char ch;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>ch;
if(ch=='1')map_[i][j]=1;
else map_[i][j]=0;
}
}
cin>>stx>>sty>>enx>>eny;
int head=1,tail=1;
x[head]=stx,y[head]=sty,z[head]=0;
used[stx][sty]=1;
while(head<=tail)
{
if(x[head]==enx&&y[head]==eny)
{
printf("%d\n",z[head]);
// break;
return 0;
}
for(int i=0;i<4;i++)
{
int tx=x[head]+dx[i];
int ty=y[head]+dy[i];
if(tx>0&&tx<=n&&ty>0&&ty<=n&&!used[tx][ty]&&!map_[tx][ty])
{
used[tx][ty]=1;
x[++tail]=tx;
y[tail]=ty;
z[tail]=z[head]+1;
}
}
head++;
}
return 0;
}
by qhzx_FeS2_Butterfly @ 2022-10-10 19:13:42
@ru_guo_lai_fo_zu 数组开小
by qhzx_FeS2_Butterfly @ 2022-10-10 19:15:38
@ru_guo_lai_fo_zu 开成1e7就行了
by liuxy1234 @ 2022-10-10 19:17:07
@ru_guo_lai_fo_zu 楼上正确,虽然n只有1e3,但是图一共有n^2个点也就是1e6,4e5空间不够
by liuxy1234 @ 2022-10-10 19:17:24
@butterflyledder3 1e7确定不会炸?
by Magus @ 2022-10-10 19:18:00
@liuxy1234 1e8都不会炸
by liuxy1234 @ 2022-10-10 19:18:46
@TX_Bernie 好像确实……不用的空间不算但是1e8还是1e9就会id return 1 ce
by Magus @ 2022-10-10 19:19:13
@liuxy1234 啊不是,1e7不会炸,1e8会
by liuxy1234 @ 2022-10-10 19:20:09
@TX_Bernie az