#include using namespace std; typedef long long int ll; typedef pair P; typedef vector VI; typedef vector VVI; #define REP(i,n) for(int i=0;i another.d;}; }; int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; int h, w; vector s(1333); ll bfs(int sx, int sy, int gx, int gy){ priority_queue q; q.push({sx,sy,0}); VVI dis(h,VI(w,INF)); dis[sx][sy]=0; vector> from(h,vector(w,xy{-1,-1})); vector> two(h,vector(w,0)); while (!q.empty()) { int x=q.top().x, y=q.top().y, d=q.top().d; q.pop(); REP(k,4){ int tox=x+dx[k], toy=y+dy[k]; if(tox<0||tox>=h||toy<0||toy>=w) continue; if(s[tox][toy]=='#') continue; if(dis[tox][toy]>d+1){ dis[tox][toy]=d+1; from[tox][toy]=xy{x,y}; two[tox][toy]=two[x][y]; q.push({tox,toy,d+1}); } else if(dis[tox][toy]==d+1){ two[tox][toy]=1; } } } if(dis[gx][gy]==INF) return -1; else if(two[gx][gy]) return dis[gx][gy]*2; else{ xy now={gx,gy}; vector> route(h,vector(w,0)); while(now.x!=-1){ route[now.x][now.y]=1; now=from[now.x][now.y]; } REP(i,h)REP(j,w){ if(route[i][j]){ if(i==sx&&j==sy) continue; if(i==gx&&j==gy) continue; REP(k,4){ int tox=i+dx[k], toy=j+dy[k]; if(!route[tox][toy]&&s[tox][toy]=='.') return dis[gx][gy]*2+2; } } } return -1; } } int main(){ int sx, sy, gx, gy; cin >> h >> w >> sx >> sy >> gx >> gy; sx--, sy--, gx--, gy--; REP(i,h) cin >> s[i]; cout << bfs(sx, sy, gx, gy) << endl; return 0; }