#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)), dp(h, vector(w, 0)); dist[ra][ca] = 0; dp[ra][ca] = 1; 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 (s[y][x] == '.') { if (dist[y][x] == -1) { dist[y][x] = dist[i][j] + 1; dp[y][x] = dp[i][j]; prev[y][x] = {i, j}; que.emplace(y, x); } else if (dist[y][x] == dist[i][j] + 1) { dp[y][x] = min(dp[y][x] + dp[i][j], 2); } } } } if (dist[rb][cb] == -1) { cout << "-1\n"; return 0; } if (dp[rb][cb] == 2) { cout << dist[rb][cb] * 2 << '\n'; return 0; } 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] == '.') { cout << dist[rb][cb] * 2 + 2 << '\n'; return 0; } } } } int ans = INF; 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; }