#include using namespace std; const int inf = (1 << 30) - 1; struct Info { vector< vector< int > > min_cost; vector< vector< int > > way; vector< vector< pair< int, int > > > from; }; const int vy[] = {-1, 0, 1, 0}; const int vx[] = {0, -1, 0, 1}; Info bfs(vector< string > &S, int SY, int SX, int DY = -1, int DX = -1) { int H = (int) S.size(); int W = (int) S[0].size(); queue< pair< int, int > > que; vector< vector< int > > min_cost(H, vector< int >(W, -1)); auto way = min_cost; vector< vector< pair< int, int > > > from(H, vector< pair< int, int > >(W, make_pair(-1, -1))); min_cost[SY][SX] = 0; way[SY][SX] = 1; que.emplace(SY, SX); while(!que.empty()) { auto p = que.front(); que.pop(); for(int k = 0; k < 4; k++) { int ny = p.first + vy[k]; int nx = p.second + vx[k]; if(ny < 0 || nx < 0 || ny >= H || nx >= W || S[ny][nx] == '#') continue; if(p.first == SY && p.second == SX && ny == DY && nx == DX) continue; if(min_cost[ny][nx] != -1) { if(min_cost[p.first][p.second] + 1 == min_cost[ny][nx]) { way[ny][nx] = min(2, way[ny][nx] + way[p.first][p.second]); } continue; } min_cost[ny][nx] = min_cost[p.first][p.second] + 1; way[ny][nx] = way[p.first][p.second]; from[ny][nx] = {p.first, p.second}; que.emplace(ny, nx); } } return (Info) {min_cost, way, from}; } int main() { int H, W, AY, AX, BY, BX; cin >> H >> W >> AY >> AX >> BY >> BX; vector< string > S(H); for(auto &s : S) cin >> s; --AY, --AX, --BY, --BX; Info beet = bfs(S, AY, AX); auto way = beet.way; auto min_cost = beet.min_cost; auto from = beet.from; if(way[BY][BX] == 0) { cout << -1 << endl; return 0; } if(way[BY][BX] == 2) { cout << min_cost[BY][BX] * 2 << endl; return 0; } vector< pair< int, int > > path; int cy = BY, cx = BX; while(cy != -1) { path.emplace_back(cy, cx); tie(cy, cx) = from[cy][cx]; } for(auto &p : path) { S[p.first][p.second] = '#'; } for(int i = 1; i + 1 < path.size(); i++) { auto &p = path[i]; for(int j = 0; j < 4; j++) { int ny = p.first + vy[j]; int nx = p.second + vx[j]; if(ny < 0 || nx < 0 || ny >= H || nx >= W || S[ny][nx] == '#') continue; if(S[ny][nx] == '.') { cout << min_cost[BY][BX] * 2 + 2 << endl; return 0; } } } auto tap = bfs(S, AY, AX).min_cost; auto ris = bfs(S, BY, BX).min_cost; int ret = inf; for(int i = 0; i < H; i++) { for(int j = 0; j < W; j++) { int near = 0; for(int k = 0; k < 4; k++) { int ny = i + vy[k]; int nx = j + vx[k]; if(ny < 0 || nx < 0 || ny >= H || nx >= W || S[ny][nx] == '#') continue; near++; } if(near >= 2) { if(tap[i][j] != -1) { ret = min(ret, min_cost[BY][BX] * 2 + tap[i][j] * 4 + 4); } if(ris[i][j] != -1) { ret = min(ret, min_cost[BY][BX] * 2 + ris[i][j] * 4 + 4); } } } } S[BY][BX] = '.'; auto nene = bfs(S, AY, AX, BY, BX).min_cost[BY][BX]; if(nene != -1) ret = min(ret, min_cost[BY][BX] + nene); cout << ret << endl; }