#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long ll; typedef pair P; int main() { int h, w; int ra, ca, rb, cb; cin>>h>>w>>ra>>ca>>rb>>cb; ra--;ca--;rb--;cb--; string s[1400]; for(int i=0; i>s[i]; } const int INF=1e8; int dx[4]={1, -1, 0, 0}, dy[4]={0, 0, 1, -1}; if(h<80 && w<80){ int d[81][81][81][81]; for(int i=0; i; queue que;que.push({{ra, ca}, {rb, cb}}); while(!que.empty()){ PP p=que.front(); que.pop(); int xa=p.first.first, ya=p.first.second, xb=p.second.first, yb=p.second.second; for(int k=0; k<4; k++){ int xa1=xa+dx[k], ya1=ya+dy[k]; if(xa1==xb && ya1==yb) continue; if(s[xa1][ya1]!='#' && d[xa1][ya1][xb][yb]>d[xa][ya][xb][yb]+1){ d[xa1][ya1][xb][yb]=d[xa][ya][xb][yb]+1; que.push({{xa1, ya1}, {xb, yb}}); } } for(int k=0; k<4; k++){ int xb1=xb+dx[k], yb1=yb+dy[k]; if(xb1==xa && yb1==ya) continue; if(s[xb1][yb1]!='#' && d[xa][ya][xb1][yb1]>d[xa][ya][xb][yb]+1){ d[xa][ya][xb1][yb1]=d[xa][ya][xb][yb]+1; que.push({{xa, ya}, {xb1, yb1}}); } } } if(d[rb][cb][ra][ca] que; que.push({ra, ca}); int d[1400][1400]; for(int i=0; id[x][y]+1){ que.push({x1, y1}); d[x1][y1]=d[x][y]+1; } } } int dr[1400][1400]; for(int i=0; idr[x][y]+1){ que.push({x1, y1}); dr[x1][y1]=dr[x][y]+1; } } } vector

v; for(int i=0; id[rb][cb]+1){ cout<<2*d[rb][cb]<2){ ans=min(ans, 2*d[rb][cb]+2); } } int e[1400][1400]; for(int i=0; ie[x][y]+1){ que.push({x1, y1}); e[x1][y1]=e[x][y]+1; } } } int e1[1400][1400]; for(int i=0; ie1[x][y]+1){ que.push({x1, y1}); e1[x1][y1]=e1[x][y]+1; } } } map mp; for(int i=0; i1){ mn=min(mn, p.first); break; } } int er[1400][1400]; for(int i=0; ier[x][y]+1){ que.push({x1, y1}); er[x1][y1]=er[x][y]+1; } } } map mp2; for(int i=0; i1){ mn=min(mn, p.first); break; } } ans=min({ans, 2*d[rb][cb]+4*mn, d[rb][cb]+e[rb][cb]}); if(ans