#include using namespace std; using pi = pair< int, int >; constexpr int inf = 1 << 30; constexpr int vy[] = {-1, 1, 0, 0}; constexpr int vx[] = {0, 0, -1, 1}; template< typename T, typename E > bool chmin(T &a, E b) { if(a > b) { a = b; return true; } else { return false; } } int main() { int H, W, Ya, Xa, Yb, Xb; cin >> H >> W >> Ya >> Xa >> Yb >> Xb; --Ya, --Xa, --Yb, --Xb; vector< string > S(H); for(auto &s : S) cin >> s; vector< vector< int > > min_cost(H, vector< int >(W, inf)); vector< vector< int > > ways(H, vector< int >(W, 0)); vector< vector< int > > from(H, vector< int >(W, -1)); { queue< pi > que; min_cost[Ya][Xa] = 0; ways[Ya][Xa] = 1; que.emplace(Ya, Xa); while(!que.empty()) { auto[y, x] = que.front(); que.pop(); for(int k = 0; k < 4; k++) { int ny = y + vy[k]; int nx = x + vx[k]; if(S[ny][nx] == '#') continue; if(chmin(min_cost[ny][nx], min_cost[y][x] + 1)) { from[ny][nx] = k; ways[ny][nx] = 0; que.emplace(ny, nx); } if(min_cost[y][x] + 1 == min_cost[ny][nx]) { ways[ny][nx] += ways[y][x]; chmin(ways[ny][nx], 2); } } } } if(ways[Yb][Xb] == 0) { cout << -1 << "\n"; return 0; } if(ways[Yb][Xb] >= 2) { cout << min_cost[Yb][Xb] * 2 << "\n"; return 0; } vector< pair< int, int > > path; int cy = Yb, cx = Xb; path.emplace_back(cy, cx); while(cy != Ya || cx != Xa) { int py = cy + vy[from[cy][cx] ^ 1]; int px = cx + vx[from[cy][cx] ^ 1]; cy = py; cx = px; path.emplace_back(cy, cx); } assert(min_cost[Yb][Xb] + 1 == path.size()); for(auto &p : path) S[p.first][p.second] = '*'; for(int i = 1; i + 1 < path.size(); i++) { for(int j = 0; j < 4; j++) { int ny = path[i].first + vy[j]; int nx = path[i].second + vx[j]; if(S[ny][nx] == '.') { cout << min_cost[Yb][Xb] * 2 + 2 << "\n"; return 0; } } } int ret = inf; { vector< vector< int > > min_cost2(H, vector< int >(W, inf)); queue< pi > que; min_cost2[Ya][Xa] = 0; que.emplace(Ya, Xa); while(!que.empty()) { auto[y, x] = que.front(); que.pop(); for(int k = 0; k < 4; k++) { int ny = y + vy[k]; int nx = x + vx[k]; if(S[ny][nx] == '#' || S[ny][nx] == '*') continue; if(chmin(min_cost2[ny][nx], min_cost2[y][x] + 1)) { que.emplace(ny, nx); } } } if(min_cost2[Yb][Xb] != inf) { chmin(ret, min_cost2[Yb][Xb] + min_cost[Ya][Xa]); } } cout << ret << "\n"; }