// 俺たちの小手先修正 #include using namespace std; int main() { int h, w; cin >> h >> w; auto to_v = [w](int y, int x) { return y * w + x; }; int Ya, Xa, Yb, Xb; cin >> Ya >> Xa >> Yb >> Xb; int a = to_v(Ya - 1, Xa - 1); int b = to_v(Yb - 1, Xb - 1); vector< string > ss(h); for (auto &s : ss) cin >> s; int V = h * w; vector< vector< int > > G(V); constexpr int dy[] = {-1, 0, 1, 0}; constexpr int dx[] = {0, 1, 0, -1}; for (int y = 1; y < h - 1; y++) { for (int x = 1; x < w - 1; x++) { if (ss[y][x] == '#') continue; int v = to_v(y, x); for (int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if (ss[ny][nx] == '#') continue; int u = to_v(ny, nx); G[v].emplace_back(u); } } } constexpr int inf = 1001001001; auto bfs = [&](int s, int t) { vector< vector< int > > res(V); res[s].emplace_back(0); struct T { int v, pre, cost; bool f; T(int v_, int pre_, int cost_, bool f_) : v(v_), pre(pre_), cost(cost_), f(f_) {} }; queue< T > que; que.emplace(s, -1, 0, false); while (not que.empty()) { auto [v, pre, cost, f] = que.front(); que.pop(); for (auto &u : G[v]) { if (u == pre) continue; if ((int)res[u].size() == 2) continue; if ((int)res[u].size() == 1 and f) continue; res[u].emplace_back(cost + 1); que.emplace(u, v, cost + 1, f or (u == t)); } } return res; }; auto da = bfs(a, b); auto db = bfs(b, a); int ans = inf; if ((int)da[b].size() == 0) { ans = -1; } if ((int)da[b].size() == 2) { ans = min(ans, da[b][0] + db[a][1]); } auto find_fromv = [&](int y, int x, const vector< vector< int > > &dist) { int f = to_v(y, x); for (int i = 0; i < 4; i++) { int u = to_v(y + dy[i], x + dx[i]); if ((int)dist[u].size() == 0) continue; if (dist[u][0] > dist[f][0]) continue; f = u; } return f; }; for (int y = 1; y < h - 1; y++) { for (int x = 1; x < w - 1; x++) { int v = to_v(y, x); if ((int)da[v].size() == 0) continue; if ((int)db[v].size() == 0) continue; if ((int)G[v].size() < 3) continue; int af = find_fromv(y, x, da); int bf = find_fromv(y, x, db); int cost = 2 * (da[v][0] + db[v][0]); if (af == bf or af == v or bf == v) { cost += 4; } else { cost += 2; } ans = min(ans, cost); } } if (ans == inf) { ans = -1; } cout << ans << endl; }