/** * date : 2020-12-20 23:57:18 */ #define NDEBUG using namespace std; // intrinstic #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // utility namespace Nyaan { using ll = long long; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; template using V = vector; template using VV = vector>; using vi = vector; using vl = vector; using vd = V; using vs = V; using vvi = vector>; using vvl = vector>; template struct P : pair { template P(Args... args) : pair(args...) {} using pair::first; using pair::second; T &x() { return first; } const T &x() const { return first; } U &y() { return second; } const U &y() const { return second; } P &operator+=(const P &r) { first += r.first; second += r.second; return *this; } P &operator-=(const P &r) { first -= r.first; second -= r.second; return *this; } P &operator*=(const P &r) { first *= r.first; second *= r.second; return *this; } P operator+(const P &r) const { return P(*this) += r; } P operator-(const P &r) const { return P(*this) -= r; } P operator*(const P &r) const { return P(*this) *= r; } }; using pl = P; using pi = P; using vp = V; constexpr int inf = 1001001001; constexpr long long infLL = 4004004004004004004LL; template int sz(const T &t) { return t.size(); } template void mem(T (&a)[N], int c) { memset(a, c, sizeof(T) * N); } template inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template int lb(const vector &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template int ub(const vector &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } constexpr long long TEN(int n) { long long ret = 1, x = 10; for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1); return ret; } template pair mkp(const T &t, const U &u) { return make_pair(t, u); } template vector mkrui(const vector &v, bool rev = false) { vector ret(v.size() + 1); if (rev) { for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1]; } else { for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; } return ret; }; template vector mkuni(const vector &v) { vector ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template vector mkord(int N, F f) { vector ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template vector reord(const vector &v, const vector &ord) { int N = v.size(); vector ret(N); for (int i = 0; i < N; i++) ret[i] = v[ord[i]]; return ret; }; template vector mkiota(int N) { vector ret(N); iota(begin(ret), end(ret), 0); return ret; } template vector mkinv(vector &v, int max_val = -1) { if (max_val < (int)v.size()) max_val = v.size() - 1; vector inv(max_val + 1, -1); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } } // namespace Nyaan // bit operation namespace Nyaan { __attribute__((target("popcnt"))) inline int popcnt(const u64 &a) { return _mm_popcnt_u64(a); } __attribute__((target("bmi"))) inline int lsb(const u64 &a) { return _tzcnt_u64(a); } __attribute__((target("bmi"))) inline int ctz(const u64 &a) { return _tzcnt_u64(a); } __attribute__((target("lzcnt"))) inline int msb(const u64 &a) { return 63 - _lzcnt_u64(a); } __attribute__((target("lzcnt"))) inline int clz64(const u64 &a) { return _lzcnt_u64(a); } template inline int gbit(const T &a, int i) { return (a >> i) & 1; } template inline void sbit(T &a, int i, bool b) { a ^= (gbit(a, i) == b ? 0 : (T(b) << i)); } constexpr long long PW(int n) { return 1LL << n; } constexpr long long MSK(int n) { return (1LL << n) - 1; } } // namespace Nyaan // inout namespace Nyaan { template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } void in() {} template void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template void outr(const T &t, const U &... u) { cout << t; outr(u...); } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; } // namespace Nyaan // debug namespace DebugImpl { template struct is_specialize : false_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize::value, void>> : true_type { }; void dump(const char& t) { cerr << t; } void dump(const string& t) { cerr << t; } template ::value, nullptr_t> = nullptr> void dump(const U& t) { cerr << t; } template void dump(const T& t, enable_if_t::value>* = nullptr) { string res; if (t == Nyaan::inf) res = "inf"; if (is_signed::value) if (t == -Nyaan::inf) res = "-inf"; if (sizeof(T) == 8) { if (t == Nyaan::infLL) res = "inf"; if (is_signed::value) if (t == -Nyaan::infLL) res = "-inf"; } if (res.empty()) res = to_string(t); cerr << res; } template void dump(const pair&); template void dump(const pair&); template void dump(const T& t, enable_if_t::value>* = nullptr) { cerr << "[ "; for (auto it = t.begin(); it != t.end();) { dump(*it); cerr << (++it == t.end() ? "" : ", "); } cerr << " ]"; } template void dump(const pair& t) { cerr << "( "; dump(t.first); cerr << ", "; dump(t.second); cerr << " )"; } template void dump(const pair& t) { cerr << "[ "; for (int i = 0; i < t.second; i++) { dump(t.first[i]); cerr << (i == t.second - 1 ? "" : ", "); } cerr << " ]"; } void trace() { cerr << endl; } template void trace(Head&& head, Tail&&... tail) { cerr << " "; dump(head); if (sizeof...(tail) != 0) cerr << ","; trace(forward(tail)...); } } // namespace DebugImpl #ifdef NyaanDebug #define trc(...) \ do { \ cerr << "## " << #__VA_ARGS__ << " = "; \ DebugImpl::trace(__VA_ARGS__); \ } while (0) #else #define trc(...) #endif // macro #define each(x, v) for (auto&& x : v) #define each2(x, y, v) for (auto&& [x, y] : v) #define all(v) (v).begin(), (v).end() #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--) #define repc(i, a, cond) for (long long i = (a); (cond); i++) #define enm(i, val, vec) \ for (long long i = 0; i < (long long)(vec).size(); i++) \ if (auto& val = vec[i]; false) \ ; \ else #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define inc(...) \ char __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define die(...) \ do { \ Nyaan::out(__VA_ARGS__); \ return; \ } while (0) namespace Nyaan { void solve(); } int main() { Nyaan::solve(); } using namespace Nyaan; vector> bfs_restore(vector>& g, int st = 0) { vector> d(g.size(), make_pair(-1, -1)); d[st] = make_pair(0, -1); queue Q; Q.push(st); while (!Q.empty()) { int cur = Q.front(); Q.pop(); int cd = d[cur].first; for (auto&& dst : g[cur]) { if (d[dst].first == -1) { d[dst].first = cd + 1; d[dst].second = cur; Q.push(dst); } } } return d; } void Nyaan::solve() { ini(H, W); ini(ra, ca, rb, cb); ra--, ca--, rb--, cb--; vs gr(H); in(gr); auto idx = [&](int i, int j) { return i * W + j; }; int ids = idx(ra, ca), idt = idx(rb, cb); V> near{mkp(1, 0), mkp(-1, 0), mkp(0, -1), mkp(0, 1)}; vvi g; auto mk = [&]() { g.clear(); g.resize(H * W); reg(i, 1, H - 1) reg(j, 1, W - 1) { if (gr[i][j] == '#') continue; if (gr[i + 1][j] == '.') g[idx(i + 1, j)].push_back(idx(i, j)); if (gr[i - 1][j] == '.') g[idx(i - 1, j)].push_back(idx(i, j)); if (gr[i][j + 1] == '.') g[idx(i, j + 1)].push_back(idx(i, j)); if (gr[i][j - 1] == '.') g[idx(i, j - 1)].push_back(idx(i, j)); } }; mk(); auto d0 = bfs_restore(g, ids); auto d1 = bfs_restore(g, idt); if (d0[idt].first == -1) die(-1); ll ans0 = d0[idt].first; vi path; for (int i = idt; i != -1; i = d0[i].second) { path.push_back(i); } each(p, path) { int hh = p / W, ww = p % W; gr[hh][ww] = '#'; } ll mn = inf; { vi d2(H * W * 2, -1); d2[idx(ra, ca)] = 0; queue Q; Q.push(ids); while (!Q.empty()) { int cur = Q.front(); Q.pop(); int codin = cur >= H * W ? cur - H * W : cur; int f = (cur != codin); int h = codin / W; int w = codin % W; trc(f,h,w); if(codin == idt) continue; int dc = d2[cur]; f |= gr[h][w] == '.'; each(dst, g[codin]) { int nh = dst / W, nw = dst % W; int nf = f | (gr[nh][nw] == '.'); if(dst == ids) nf = 0; trc(nf, nh , nw); int nid = nf * H * W + idx(nh, nw); if (d2[nid] == -1) { d2[nid] = dc + 1; Q.push(nid); } } } if (d2[H * W + idt] != -1) amin(mn, d2[H * W + idt]); } trc(mn); each(x, gr) trc(x); bool nukemiti = 0, mawarimiti = 0; int mws = 0, mwt = 0; vi mwrs; each(p, path) { int hh = p / W, ww = p % W; trc(hh, ww); each2(dh, dw, near) if (gr[hh + dh][ww + dw] == '.') { if (p != ids and p != idt) nukemiti = true; else { mawarimiti = true, mwrs.push_back(idx(hh + dh, ww + dw)); if (ids == p) mws++; if (idt == p) mwt++; } } } if (!nukemiti and !mawarimiti) die(-1); if (nukemiti) { out(ans0 + min(ans0 + 2, mn)); return; } trc(mws, mwt); if (mws >= 2 or mwt >= 2) { out(ans0 + min(ans0 + 4, mn)); return; exit(1); } // 廻り道のみオーケー 実装したくないな 困った // 分岐3箇所あるマスに行く感じか?自信ねえ mk(); // 回り道出来るマスは? ll mrval = inf; // g[ra][ca] = g[rb][cb] = '.'; each(p, mwrs) { auto d2 = bfs_restore(g, p); rep(i, H) rep(j, W) { if (gr[i][j] == '#') continue; int id = idx(i, j); if (d2[id].first == -1) continue; int masu = 0; each2(di, dj, near) masu += gr[i + di][j + dj] == '.'; if (p == idx(i, j) and masu >= 2) mrval = 0; if (masu <= 2) continue; amin(mrval, d2[id].first); } } trc(mrval); // 二人ともmrval + 1に行く -> 戻るの手間が余計にかかる if (mn == inf and mrval == inf) die(-1); amin(mn, (mrval + 2) * 4 + ans0); out(ans0 + mn); }