#define _USE_MATH_DEFINES #include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 1000000007; // constexpr int MOD = 998244353; constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1}; template inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; } template inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; int main() { int h, w, ra, ca, rb, cb; cin >> h >> w >> ra >> ca >> rb >> cb; --ra; --ca; --rb; --cb; vector s(h); REP(i, h) cin >> s[i]; vector dist(h, vector(w, -1)); dist[ra][ca] = 0; vector prev(h, vector(w, make_pair(-1, -1))); queue> que({{ra, ca}}); while (!que.empty()) { auto [i, j] = que.front(); que.pop(); REP(k, 4) { int y = i + dy[k], x = j + dx[k]; if (dist[y][x] == -1 && s[y][x] == '.') { dist[y][x] = dist[i][j] + 1; prev[y][x] = {i, j}; que.emplace(y, x); } } } if (dist[rb][cb] == -1) { cout << "-1\n"; return 0; } int ans = INF; // { // int cnt = 0; // REP(k, 4) { // int y = ra + dy[k], x = ca + dx[k]; // cnt += s[y][x] == '.'; // } // if (cnt >= 3) chmin(ans, dist[rb][cb] * 2 + 4); // } // { // int cnt = 0; // REP(k, 4) { // int y = rb + dy[k], x = cb + dx[k]; // cnt += s[y][x] == '.'; // } // if (cnt >= 3) chmin(ans, dist[rb][cb] * 2 + 4); // } s[rb][cb] = 'b'; int cr = rb, cc = cb; while (cr != ra || cc != ca) { tie(cr, cc) = prev[cr][cc]; s[cr][cc] = '$'; } s[ra][ca] = 'a'; REP(i, h) REP(j, w) { if (s[i][j] == '$') { REP(k, 4) { int y = i + dy[k], x = j + dx[k]; if (s[y][x] == '.') chmin(ans, dist[rb][cb] * 2 + 2); } } } s[ra][ca] = s[rb][cb] = '$'; // REP(i, h) cout << s[i] << '\n'; // 迂回路を探索しているが嘘解法? vector bfs(h, vector(w, make_pair(-1, -1))); queue> que2; REP(i, h) REP(j, w) { if (s[i][j] == '$') { bfs[i][j] = {dist[i][j], 0}; que2.emplace(i, j, dist[i][j]); } } while (!que2.empty()) { auto [i, j, d] = que2.front(); que2.pop(); REP(k, 4) { int y = i + dy[k], x = j + dx[k]; if (s[y][x] == '.') { if (bfs[y][x].first == -1) { bfs[y][x] = {d, bfs[i][j].second + 1}; que2.emplace(y, x, d); } else if (bfs[y][x].first != bfs[i][j].first) { int tmp = bfs[y][x].second + bfs[i][j].second + 1 - abs(bfs[y][x].first - bfs[i][j].first); assert(tmp >= 0); chmin(ans, dist[rb][cb] * 2 + tmp); } } } } vector dista(h, vector(w, -1)); dista[ra][ca] = 0; que.emplace(ra, ca); while (!que.empty()) { auto [i, j] = que.front(); que.pop(); int cnt = 0; REP(k, 4) { int y = i + dy[k], x = j + dx[k]; if (s[y][x] != '#') { ++cnt; if (dista[y][x] == -1) { dista[y][x] = dista[i][j] + 1; que.emplace(y, x); } } } if (cnt >= 3) chmin(ans, dist[rb][cb] * 2 + (dista[i][j] + 1) * 4); } vector distb(h, vector(w, -1)); distb[rb][cb] = 0; que.emplace(rb, cb); while (!que.empty()) { auto [i, j] = que.front(); que.pop(); int cnt = 0; REP(k, 4) { int y = i + dy[k], x = j + dx[k]; if (s[y][x] != '#') { ++cnt; if (distb[y][x] == -1) { distb[y][x] = distb[i][j] + 1; que.emplace(y, x); } } } if (cnt >= 3) chmin(ans, dist[rb][cb] * 2 + (distb[i][j] + 1) * 4); } cout << (ans == INF ? -1 : ans) << '\n'; return 0; }