#include #include #include using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001 long long d[2005][2005]; int main(){ int N,M; cin>>N>>M; int sx,sy,gx,gy; cin>>sx>>sy>>gx>>gy; sx--,sy--,gx--,gy--; vector s(N); rep(i,N)cin>>s[i]; rep(i,N){ rep(j,M){ d[i][j] = Inf64; } } vector pre(N+1,vector(M,0)); for(int i=1;i>; priority_queue,greater

> Q; Q.emplace(0,make_pair(sx,sy)); d[sx][sy] = 0; while(Q.size()>0){ long long D = Q.top().first; int x = Q.top().second.first; int y = Q.top().second.second; Q.pop(); if(D!=d[x][y])continue; if(s[x][y]=='.'){ if(y!=0){ int xx = 0,yy = y-1; xx = pre[x+1][yy]; long long DD = D; if(d[xx][yy]>DD){ d[xx][yy] = DD; Q.emplace(DD,make_pair(xx,yy)); } } if(y!=M-1){ int xx = 0,yy = y+1; xx = pre[x+1][yy]; long long DD = D; if(d[xx][yy]>DD){ d[xx][yy] = DD; Q.emplace(DD,make_pair(xx,yy)); } } for(int l=-1;l<=1;l+=2){ if(y+l<0||y+l>=M)continue; int tx = x+1; int ty = y+l; tx = pre[tx][ty]; for(int k=-2;k<=2;k+=2){ if(abs(l-k)!=1)continue; int xx = 0,yy = y+k; if(yy<0||yy>=M)continue; xx = tx + 1 + (max(0,(x-tx))/2); xx = min(xx,N); xx = pre[xx][yy]; long long DD = D; if(d[xx][yy]>DD){ d[xx][yy] = DD; Q.emplace(DD,make_pair(xx,yy)); } } } for(int l=-1;l<=1;l+=2){ if(y+l<0||y+l>=M)continue; int tx = x+1; int ty = y+l; tx = pre[tx][ty]; for(int k=-2;k<=2;k+=2){ if(abs(l-k)!=1)continue; int xx = 0,yy = y+k; if(yy<0||yy>=M)continue; xx = tx + 1 + (max(0,(x-tx))); xx = min(xx,N); xx = pre[xx][yy]; long long DD = D+1; if(d[xx][yy]>DD){ d[xx][yy] = DD; Q.emplace(DD,make_pair(xx,yy)); } } } } if(x!=0){ int xx = x-1,yy = y; long long DD = D; if(d[xx][yy]>DD){ d[xx][yy] = DD; Q.emplace(DD,make_pair(xx,yy)); } } } /* rep(i,N){ rep(j,M){ cout<