#include #include #include #include #include using namespace std; struct nodes{ int x; int y; }; int main(){ //1. 入力を読む int H,W; cin >> H >> W; int sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy; sx--; sy--; gx--; gy--; vector S(H); for (int i = 0; i < H; i++){ cin >> S[i]; } assert(S[sx][sy] == '#'); assert(S[gx][gy] == '#'); //2. 全ての座標に対して,その真下にある座標で一番上にあるものがどこかのx座標を求める vector calc_highest_x(W, H - 1); vector> highest_x(H, vector(W, H - 1)); for (int i = H - 2; i >= 0; i--){ for (int j = 0; j < W; j++){ if (S[i][j] == '#') calc_highest_x[j] = i; highest_x[i][j] = calc_highest_x[j]; } } int INF = 1 << 24; //3. 01-BFSを行う vector> isvisited(H, vector(W, false)); vector> dist(H, vector(W, INF)); deque dq; dq.push_front(nodes{sx, sy}); dist[sx][sy] = 0; while(dq.size()){ nodes p = dq.front(); dq.pop_front(); if (isvisited[p.x][p.y]){ continue; } isvisited[p.x][p.y] = true; //1回の移動で行ける範囲を探索 if (p.y - 1 >= 0){ int next_x = max(0, p.x - 1); next_x = highest_x[next_x][p.y - 1]; dq.push_front(nodes{next_x, p.y - 1}); dist[next_x][p.y - 1] = min(dist[next_x][p.y - 1], dist[p.x][p.y]); } if (p.y + 1 < W){ int next_x = max(0, p.x - 1); next_x = highest_x[next_x][p.y + 1]; dq.push_front(nodes{next_x, p.y + 1}); dist[next_x][p.y + 1] = min(dist[next_x][p.y + 1], dist[p.x][p.y]); } //2回の移動で行ける範囲を探索 if (p.y - 2 >= 0){ int next_x = max(0, p.x - 1); next_x = highest_x[next_x][p.y - 2]; dq.push_back(nodes{next_x, p.y - 2}); dist[next_x][p.y - 2] = min(dist[next_x][p.y - 2], dist[p.x][p.y] + 1); } if (p.y - 2 >= 0){ int diffs_x = highest_x[p.x][p.y - 1] - p.x; int next_x = highest_x[p.x][p.y - 1] - 1 - diffs_x / 2; next_x = highest_x[max(0, next_x)][p.y - 2]; dq.push_front(nodes{next_x, p.y - 2}); dist[next_x][p.y - 2] = min(dist[next_x][p.y - 2], dist[p.x][p.y]); } if (p.y + 2 < W){ int next_x = max(0, p.x - 1); next_x = highest_x[next_x][p.y + 2]; dq.push_back(nodes{next_x, p.y + 2}); dist[next_x][p.y + 2] = min(dist[next_x][p.y + 2], dist[p.x][p.y] + 1); } if (p.y + 2 < W){ int diffs_x = highest_x[p.x][p.y + 1] - p.x; int next_x = highest_x[p.x][p.y + 1] - 1 - diffs_x / 2; next_x = highest_x[max(0, next_x)][p.y + 2]; dq.push_front(nodes{next_x, p.y + 2}); dist[next_x][p.y + 2] = min(dist[next_x][p.y + 2], dist[p.x][p.y]); } if (p.y >= 0 && p.y < W){ int next_x = max(0, p.x - 1); next_x = highest_x[next_x][p.y]; dq.push_back(nodes{next_x, p.y}); dist[next_x][p.y] = min(dist[next_x][p.y], dist[p.x][p.y] + 1); } } if (dist[gx][gy] == INF) cout << -1 << endl; else cout << dist[gx][gy] << endl; }