#include #include #include #include #include #include #include using namespace std; template inline void for_nbd4(int x, int y, int lx, int ux, int ly, int uy, Callback f) { constexpr pair dxdy[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; for (auto [dx, dy] : dxdy) { const int u = x + dx, v = y + dy; if (lx <= u && u < ux && ly <= v && v < uy) f(u, v); } } template inline void for_nbd4(int x, int y, int X, int Y, Callback f) { for_nbd4(x, y, 0, X, 0, Y, f); } template inline T sum_nbd4(int x, int y, int lx, int ux, int ly, int uy, Callback f) { constexpr pair dxdy[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; T result{}; for (auto [dx, dy] : dxdy) { const int u = x + dx, v = y + dy; if (lx <= u && u < ux && ly <= v && v < uy) result += f(u, v); } return result; } template inline T sum_nbd4(int x, int y, int X, int Y, Callback f) { return sum_nbd4(x, y, 0, X, 0, Y, f); } constexpr int INF = 1<<30; int solve(vector S, int sx, int sy, int gx, int gy) { const int h = S.size(), w = S.front().size(); int dist[h][w], count[h][w]; pair from[h][w]; queue > q; q.emplace(sx, sy); for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) if (i == sx && j == sy) { dist[i][j] = 0; count[i][j] = 1; from[i][j] = {-1, -1}; } else { dist[i][j] = INF; count[i][j] = 0; } while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for_nbd4(x, y, h, w, [x=x, y=y, &S, &dist, &q, &count, &from](int u, int v) { if (S[u][v] == '#') return; if (dist[u][v] > dist[x][y] + 1) { dist[u][v] = dist[x][y] + 1; count[u][v] = count[x][y]; from[u][v] = {x, y}; q.emplace(u, v); } else if (dist[u][v] == dist[x][y] + 1) { assert(count[u][v] > 0); assert(count[x][y] > 0); count[u][v] = 2; } }); } // for (int i = 0; i < h; i++) // for (int j = 0; j < w; j++) // cerr << i << ' ' << j << ' ' << dist[i][j] << ' ' << count[i][j] << endl; auto is_empty = [&S](int u, int v) -> int {return int(S[u][v] == '.');}; if (count[gx][gy] == 0) return -1; else if (count[gx][gy] > 1) return 2 * dist[gx][gy]; else { for (int x = gx, y = gy;;) { tie(x, y) = from[x][y]; if (x == sx && y == sy) break; if (sum_nbd4(x, y, h, w, is_empty) > 2) { return 2 * dist[gx][gy] + 2; } } const int d0 = dist[gx][gy]; int ans = INF; for (int i = 0; i < h; i++) fill(dist[i], dist[i] + w, INF); q.emplace(sx, sy); q.emplace(gx, gy); dist[sx][sy] = 0; dist[gx][gy] = 0; // cerr << string(10, '-') << endl; while (!q.empty()) { auto [x, y] = q.front(); // cerr << x << ' ' << y << endl; q.pop(); if (sum_nbd4(x, y, h, w, is_empty) > 2) { const int d1 = dist[x][y]; ans = min(ans, 2 * d0 + 4 * (d1 + 1)); break; } for_nbd4(x, y, h, w, [x=x, y=y, &dist, &q, &S](int u, int v) { if (S[u][v] == '.' && dist[u][v] == INF) { dist[u][v] = dist[x][y] + 1; q.emplace(u, v); } }); } for (int x = gx, y = gy;;) { tie(x, y) = from[x][y]; if (x == sx && y == sy) break; S[x][y] = '#'; } for (int i = 0; i < h; i++) fill(dist[i], dist[i] + w, INF); for_nbd4(sx, sy, h, w, [gx, gy, &q, &dist, &S](int u, int v) { if (S[u][v] == '.' && (u != gx || v != gy)) { q.emplace(u, v); dist[u][v] = 1; } }); while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for_nbd4(x, y, h, w, [x=x, y=y, sx, sy, gx, gy, &S, &dist, &q](int u, int v) { if (S[u][v] == '#') return; if (u == sx && v == sy) return; if (dist[u][v] > dist[x][y] + 1) { dist[u][v] = dist[x][y] + 1; q.emplace(u, v); } }); } ans = min(ans, d0 + dist[gx][gy]); return (ans == INF ? -1 : ans); } } int dp(const vector& S, int sx, int sy, int gx, int gy) { const int h = S.size(), w = S.front().size(); int dp[h][w][h][w]; for (int a = 0; a < h; a++) for (int b = 0; b < w; b++) for (int c = 0; c < h; c++) for (int d = 0; d < w; d++) dp[a][b][c][d] = INF; queue > q; dp[sx][sy][gx][gy] = 0; q.emplace(sx, sy, gx, gy); while (!q.empty()) { auto [a, b, c, d] = q.front(); q.pop(); const int dist = dp[a][b][c][d]; for_nbd4(a, b, h, w, [c=c, d=d, dist, &dp, &S, &q](int u, int v) { if (S[u][v] == '#') return; if (c == u && d == v) return; if (dp[u][v][c][d] > dist + 1) { dp[u][v][c][d] = dist + 1; q.emplace(u, v, c, d); } }); for_nbd4(c, d, h, w, [a=a, b=b, dist, &dp, &S, &q](int u, int v) { if (S[u][v] == '#') return; if (a == u && b == v) return; if (dp[a][b][u][v] > dist + 1) { dp[a][b][u][v] = dist + 1; q.emplace(a, b, u, v); } }); } return dp[gx][gy][sx][sy] == INF ? -1 : dp[gx][gy][sx][sy]; } int main() { int h, w, sx, sy, gx, gy; cin >> h >> w >> sx >> sy >> gx >> gy; sx--; sy--; gx--; gy--; vector S(h); for (int i = 0; i < h; i++) cin >> S[i]; cout << solve(S, sx, sy, gx, gy) << endl; // int h = 6, w = 6; // vector S(h, string(w, '#')); // const int k = (h - 2) * (w - 2); // for (int s = 0; s < 1<> idx) & 1) == 1 ? '#' : '.'); // idx++; // assert(idx <= k); // } // for (int a = 1; a < h-1; a++) // for (int b = 1; b < w-1; b++) { // if (S[a][b] == '#') continue; // for (int c = 1; c < h-1; c++) // for (int d = 1; d < w-1; d++) { // if (S[c][d] == '#') continue; // if (a == c && b == d) continue; // int ans = solve(S, a, b, c, d), // ans2 = dp(S, a, b, c, d); // if(ans != ans2) { // cerr << a << ' ' << b << ' ' << c << ' ' << d << endl; // S[a][b] = 'A'; // S[c][d] = 'B'; // for (string &line : S) cerr << line << endl; // cout << " ==> " << ans << ' ' << ans2 << endl; // S[a][b] = '.'; // S[c][d] = '.'; // return 0; // } // } // } // } }