#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 bfs1(h, vector(w, -1)); vector bfs2(h, vector(w, vector{})); vector>> que2; REP(i, h) REP(j, w) { if (s[i][j] == '$') { bfs1[i][j] = 0; bfs2[i][j] = {dist[i][j]}; que2.emplace_back(i, j, vector{dist[i][j]}); } } while (!que2.empty()) { map, vector> nx_mp; for (auto [i, j, ds] : que2) { int nx_dist = bfs1[i][j] + 1; REP(k, 4) { int y = i + dy[k], x = j + dx[k]; if (s[y][x] == '.') { if (bfs1[y][x] == -1) { bfs1[y][x] = nx_dist; bfs2[y][x] = ds; nx_mp[{y, x}] = ds; } else if (bfs1[y][x] == nx_dist) { for (int a : ds) for (int b : bfs2[y][x]) { if (a != b) { int tmp = bfs1[y][x] + nx_dist - abs(a - b); assert(tmp >= 0); chmin(ans, dist[rb][cb] * 2 + tmp); nx_mp[{y, x}].emplace_back(a); } } } else { for (int a : ds) for (int b : bfs2[y][x]) { if (a != b) { int tmp = bfs1[y][x] + nx_dist - abs(a - b); assert(tmp >= 0); chmin(ans, dist[rb][cb] * 2 + tmp); } } } } } } que2.clear(); for (auto [ij, ds] : nx_mp) que2.emplace_back(ij.first, ij.second, ds); } cout << (ans == INF ? -1 : ans) << '\n'; return 0; }