#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; } } using P = pair>; 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(x!=N-1&&y!=0){ int xx = x+1,yy = y-1; if(s[xx][yy]=='.'){ long long DD = D; if(d[xx][yy]>DD){ d[xx][yy] = DD; Q.emplace(DD,make_pair(xx,yy)); } } } if(x!=N-1&&y!=M-1){ int xx = x+1,yy = y+1; if(s[xx][yy]=='.'){ long long DD = D; if(d[xx][yy]>DD){ d[xx][yy] = DD; Q.emplace(DD,make_pair(xx,yy)); } } } for(int k=-2;k<=2;k+=2){ int xx = 1 + x/2,yy = y+k; if(y<0||y>=M)continue; long long DD = D; if(d[xx][yy]>DD){ d[xx][yy] = DD; Q.emplace(DD,make_pair(xx,yy)); } } for(int k=-2;k<=2;k+=2){ int xx = min(N-1,1 + x),yy = y+k; if(y<0||y>=M)continue; 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<