Submission #64520226

---

Source Code Expand

#include<bits/stdc++.h>
#define int long long
#define FastIO
#ifdef FastIO
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin)),*p2=0,*p1++)
#endif //#ifdef FastIO
using namespace std;int n,m,k;
namespace IO{char buf[8888888],*p1=buf,*p2=buf,ibuf;
int rd(int x=0,int f=1){for(;!isdigit(ibuf);ibuf=getchar())ibuf=='-'&&(f=-1);for(;isdigit(ibuf);ibuf=getchar())x=(x<<1)+(x<<3)+(ibuf^48);return x*f;}
int rds(char*s,int n=0){for(;!isgraph(ibuf);ibuf=getchar());for(;isgraph(ibuf);ibuf=getchar())s[n++]=ibuf;return s[n]=0,n;}
}using IO::rd;using IO::rds;//namespace IO
#define fio(s) (freopen(s".in","r",stdin),freopen(s".out","w",stdout))

int a[1000100];
char s[1010][1010];
int d[1010][1010];
int dx[8]={-1,0,1,0,-2,0,2,0};
int dy[8]={0,-1,0,1,0,-2,0,2};
bool vis[1010][1010];

signed main(){int Tst=1;
//Tst=rd();
while(Tst--){

	n=rd();m=rd();n+=2,m+=2;
	for(int i=2;i<n;i++)rds(s[i]+2);
	int a=rd()+1,b=rd()+1,c=rd()+1,D=rd()+1;
	memset(d,-1,sizeof(d));
	deque<int>Q;Q.push_back(a<<32|b);
	d[a][b]=0;
	while(!Q.empty())
	{
		int x=Q.front()>>32,y=signed(Q.front());Q.pop_front();
		if(vis[x][y])continue;
		vis[x][y]=1;
		for(int k=0;k<4;k++)
		{
			int xx=x+dx[k],yy=y+dy[k];
			if(xx<2||yy<2||xx>=n||yy>=m)continue;
			if(s[xx][yy]=='#')continue;
			if(~d[xx][yy])if(d[xx][yy]<=d[x][y])continue;
			d[xx][yy]=d[x][y],Q.push_front(xx<<32|yy);
		}
		for(int k=0;k<8;k++)
		{
			int xx=x+dx[k],yy=y+dy[k];
			if(xx<2||yy<2||xx>=n||yy>=m)continue;
			if(~d[xx][yy])continue;
			d[xx][yy]=d[x][y]+1,Q.push_back(xx<<32|yy);
		}
	}
	cout<<d[c][D]<<endl;

//newline!
}return 0;}

Submission Info

Judge Result