#include using namespace std; int H, W, ax, ay, bx, by; vector S; int main() { cin >> H >> W >> ax >> ay >> bx >> by; ax--; ay--; bx--; by--; S.resize(H); for (int i = 0; i < H; i++) { cin >> S[i]; for (auto& c : S[i]) if (c == '#') c = 1; else c = 0; } const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, -1, 0, 1}; queue>> que; que.push(make_pair(0, make_pair(ax, ay))); vector> dist(H, vector(W, -1)); dist[ax][ay] = 0; que.push(make_pair(0, make_pair(ax, ay))); while (!que.empty()) { auto p = que.front(); que.pop(); int d = p.first, now_x = p.second.first, now_y = p.second.second; if (now_x == bx && now_y == by) continue; for (int i = 0; i < 4; i++) { int nxt_x = now_x + dx[i], nxt_y = now_y + dy[i]; if (S[nxt_x][nxt_y] == 1) { continue; } if (dist[nxt_x][nxt_y] == -1) { dist[nxt_x][nxt_y] = d + 1; que.push(make_pair(d + 1, make_pair(nxt_x, nxt_y))); } } } if (dist[bx][by] == -1) { cout << -1 << endl; return 0; } bool flag1 = false, flag2 = false; int now_x = bx, now_y = by, now_dist = dist[bx][by]; while (!(now_x == ax && now_y == ay)) { int cnt1 = 0, cnt2 = 0, tmp_x, tmp_y; for (int i = 0; i < 4; i++) { int nxt_x = now_x + dx[i], nxt_y = now_y + dy[i]; if (dist[nxt_x][nxt_y] == now_dist - 1) { cnt1++; tmp_x = nxt_x; tmp_y = nxt_y; } if (S[nxt_x][nxt_y] == 0) cnt2++; } if (cnt1 >= 2) flag1 = true; if (now_dist != dist[bx][by]) if (cnt2 >= 3) flag2 = true; now_x = tmp_x; now_y = tmp_y; now_dist--; } if (flag1) { cout << dist[bx][by] * 2 << endl; } else if (flag2) { cout << dist[bx][by] * 2 + 2 << endl; } else { int ans = 1e9; //case 3 vector d; for (int i = 0; i < 4; i++) { int tmp = dist[bx + dx[i]][by + dy[i]]; if (tmp != -1) d.emplace_back(tmp); } sort(d.begin(), d.end()); if (d.size() >= 2) { ans = min(ans, d[0] + d[1] + 2); } //case 1 for (int x = 1; x < H - 1; x++) { for (int y = 1; y < W - 1; y++) { if (dist[x][y] <= 0) continue; int cnt = 0; for (int i = 0; i < 4; i++) { int nxt_x = x + dx[i], nxt_y = y + dy[i]; if (dist[nxt_x][nxt_y] == -1) continue; cnt += (dist[nxt_x][nxt_y] == dist[x][y] + 1); } if (cnt >= 2) ans = min(ans, dist[bx][by] * 2 + dist[x][y] * 4 + 4); } } //case 4 for (int x = 1; x < H - 1; x++) { for (int y = 1; y < W - 1; y++) { if (dist[x][y] <= 0) continue; int cnt = 0; for (int i = 0; i < 4; i++) { int nxt_x = x + dx[i], nxt_y = y + dy[i]; if (dist[nxt_x][nxt_y] == -1) continue; cnt += (dist[nxt_x][nxt_y] == dist[x][y] - 1); } if (cnt >= 2) ans = min(ans, dist[bx][by] * 2 + dist[x][y] * 4); } } //case 2 { swap(ax, bx); swap(ay, by); queue>> que; que.push(make_pair(0, make_pair(ax, ay))); vector> dist(H, vector(W, -1)); dist[ax][ay] = 0; que.push(make_pair(0, make_pair(ax, ay))); while (!que.empty()) { auto p = que.front(); que.pop(); int d = p.first, now_x = p.second.first, now_y = p.second.second; if (now_x == bx && now_y == by) continue; for (int i = 0; i < 4; i++) { int nxt_x = now_x + dx[i], nxt_y = now_y + dy[i]; if (S[nxt_x][nxt_y] == 1) { continue; } if (dist[nxt_x][nxt_y] == -1) { dist[nxt_x][nxt_y] = d + 1; que.push(make_pair(d + 1, make_pair(nxt_x, nxt_y))); } } } for (int x = 1; x < H - 1; x++) { for (int y = 1; y < W - 1; y++) { if (dist[x][y] <= 0) continue; int cnt = 0; for (int i = 0; i < 4; i++) { int nxt_x = x + dx[i], nxt_y = y + dy[i]; if (dist[nxt_x][nxt_y] == -1) continue; cnt += (dist[nxt_x][nxt_y] == dist[x][y] + 1); } if (cnt >= 2) ans = min(ans, dist[bx][by] * 2 + dist[x][y] * 4 + 4); } } for (int x = 1; x < H - 1; x++) { for (int y = 1; y < W - 1; y++) { if (dist[x][y] <= 0) continue; int cnt = 0; for (int i = 0; i < 4; i++) { int nxt_x = x + dx[i], nxt_y = y + dy[i]; if (dist[nxt_x][nxt_y] == -1) continue; cnt += (dist[nxt_x][nxt_y] == dist[x][y] - 1); } if (cnt >= 2) ans = min(ans, dist[bx][by] * 2 + dist[x][y] * 4); } } } if (ans == (int)1e9) ans = -1; cout << ans << endl; } }