#ifndef _GLIBCXX_NO_ASSERT #include #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if __cplusplus >= 201103L #include #include #include #include #include #include #include #include #include #endif #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 #if __cplusplus >= 201103L #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #endif using namespace std; using i32 = int; using i64 = long long; using vi32 = vector; using vi64 = vector; using vvi32 = vector; using vvi64 = vector; using pii32 = pair; using pii64 = pair; #define ALL(obj) (obj).begin(),(obj).end() #define bit(n) (1LL<<(n)) #define cauto const auto& #define CLR(ar,val) memset(ar, val, sizeof(ar)) #define FOR(i,a,b) for(i32 i=(a); i<(i32)(b); i++) #define PRINT(n) cout << (n) <<"\n"; #define RALL(obj) ((obj).rbegin(),(obj).rend()) #define REP(i,n) FOR(i,0,n) #define SZ(obj) ((i32)(obj).size()) #define UNIQUE(v) (v).erase( unique(ALL(v)),v.end() ); #define mp make_pair #define pb push_back static const double PI = 3.1415926535897932; static const double E = 2.7182818284590452; static const double EPS = 1e-14; static const int INF = 0x3F3F3F3F; static const i64 INFLL = 1e18; static const i64 MOD = (i64) 1e9 + 7; int dy[4] = {1, 0, -1, 0}; int dx[4] = {0, 1, 0, -1}; /*** 最大値、最小値を更新する関数 ***/ template inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } //拡張ユークリッドの互除法 /*** x, y に gcd(a, b) = a * x + b * y を満たすx, yを代入して最大公約数が返される ***/ template T extgcd(T a, T b, T &x, T &y) { T d = a; if(b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } //進数変換 /*** 10進数xをb進数に変換する ***/ template vector convert_base(T x, T b) { vector ret; T t = 1, k = abs(b); while (x) { ret.emplace_back((x * t) % k); if (ret.back() < 0) ret.back() += k; x -= ret.back() * t; x /= k; t *= b / k; } if (ret.empty()) ret.emplace_back(0); reverse(all(ret)); return ret; } //ポップカウント /*** 32bit整数において2進数表示したときの1の数を返してくれる関数 ***/ i32 popCount(i32 data){ data = (data & 0x55555555) + ((data & 0xAAAAAAAA) >> 1); data = (data & 0x33333333) + ((data & 0xCCCCCCCC) >> 2); data = (data & 0x0F0F0F0F) + ((data & 0xF0F0F0F0) >> 4); data = (data & 0x00FF00FF) + ((data & 0xFF00FF00) >> 8); data = (data & 0x0000FFFF) + ((data & 0xFFFF0000) >> 16); return data; } /*** unsigned intを渡すと bit reverseしてくれる関数 ***/ unsigned int bitReverse(unsigned int data){ data = ((data & 0x55555555) << 1) | ((data & 0xAA555555) >> 1); data = ((data & 0x33333333) << 2) | ((data & 0xCCCCCCCC) >> 2); data = ((data & 0x0F0F0F0F) << 4) | ((data & 0xF0F0F0F0) >> 4); data = ((data & 0x00FF00FF) << 8) | ((data & 0xFF00FF00) >> 8); data = (data << 16) | (data >> 16); return data; } /*** オイラーのφ関数 ***/ i64 euler_phi(i64 n){ i64 ret = n; for (i64 i = 2; i * i <= n; i++) { if (n % i == 0) { ret -= ret / i; while (n % i == 0) n /= i; } } if (n > 1) ret -= ret / n; return ret; } /*** オイラーのφ関数の表 ***/ vi32 euler_phi_table(i32 n) { vi32 euler(n + 1); for(i32 i = 0; i <= n; i++) { euler[i] = i; } for(i32 i = 2; i <= n; i++) { if(euler[i] == i) { for(i32 j = i; j <= n; j += i) { euler[j] = euler[j] / i * (i - 1); } } } return euler; } /*** べき乗(x ^ n)をmodで割ったあまりを計算してくれる関数 ***/ i64 power(i64 x, i64 n, i64 mod) { i64 ret = 1; while (n > 0) { if (n & 1) (ret *= x) %= mod; (x *= x) %= mod; n >>= 1; } return ret; } /*** long long型整数を入れると 約数を配列にして返してくれる関数 ***/ vi64 divisor(i64 n) { vi64 ret; for(i64 i = 1; i * i <= n; i++) { if(n % i == 0) { ret.push_back(i); if(i * i != n) ret.push_back(n / i); } } sort(ALL(ret)); return (ret); } /*** long long型整数を入れると 素数ならtrue 合成数ならfalse を返してくれる関数 ***/ bool is_prime(i64 x) { for(i64 i = 2; i * i <= x; i++) { if(x % i == 0) return false; } return true; } vector sieve_of_eratosthenes(i32 n) { vector primes(n+1, true); primes[0] = primes[1] = false; for (i32 i = 2; i*(i64)i <= n; ++i) if (primes[i]) for (i32 k = i+i; k <= n; k += i) primes[k] = false; return primes; } /*** 配列vと区間kを与えると v[0] - v[k] v[1] - v[k+1] v[2] - v[k+2] の区間ごとの最小値を配列に入れて返してくれる関数 ***/ template vector slide_min(const vector& v, i32 k) { deque deq; vector ret; for (i32 i = 0; i < SZ(v); i++) { while(!deq.empty() && v[deq.back()] >= v[i]) { deq.pop_back(); } deq.push_back(i); if(i-k+1 >= 0) { ret.emplace_back(v[deq.front()]); if(deq.front() == i - k + 1) deq.pop_front(); } } return ret; } /*** a, b, pに対し a ^ x === b (mod p)を満たす非負整数 xを求める関数 ***/ i64 mod_log(i64 a, i64 b, i64 p) { i64 ok = p, ng = -1; while(ok - ng > 1) { auto mid = (ok + ng) / 2; if (mid * mid >= p) ok = mid; else ng = mid; } unordered_map baby; baby.reserve(ok); i64 factor = 1; for (i64 i = 0, e = b; i < ok; i++) { baby[e] = i; (factor *= a) %= p; (e *= a) %= p; } for (i64 i = 1, e = factor; i <= ok; i++) { auto it = baby.find(e); if (it != baby.end()) return i * ok - it -> second; (e *= factor) %= p; } return -1; } // 最大公約数 uint32_t euclidean_gcd(uint32_t a, uint32_t b) { while(a^=b^=a^=b%=a); return b; } // 最小公倍数 uint32_t euclidean_lcm(uint32_t a, uint32_t b) { return a * b / euclidean_gcd(a, b); } // カタラン数 unsigned long int catalan[200500]; unsigned long int catalanDP(unsigned int n) { catalan[0] = catalan[1] = 1; for (unsigned int i = 2; i <= n; i++) { catalan[i] = 0; for (unsigned int j = 0; j < i; j++) catalan[i] += catalan[j] * catalan[i - j - 1]; } return catalan[n]; } i32 qp(i32 a, i64 b) { i32 ans = 1; do { if (b&1) ans = 1ll * ans * a % MOD; a = 1ll * a * a % MOD; } while (b >>= 1); return ans; } i32 qp(i32 a, i64 b, i32 mo) { i32 ans = 1; do { if (b&1) ans = 1ll * ans * a % mo; a = 1ll * a * a % mo; } while (b>>=1); return ans; } // NTT namespace NumberTheoreticTransform{ constexpr i64 NTT_PRIMES[][2] = { {1224736769, 3}, // 2^24 * 73 + 1, {1053818881, 7}, // 2^20 * 3 * 5 * 67 + 1 {1051721729, 6}, // 2^20 * 17 * 59 + 1 {1045430273, 3}, // 2^20 * 997 + 1 {1012924417, 5}, // 2^21 * 3 * 7 * 23 + 1 {1007681537, 3}, // 2^20 * 31^2 + 1 {1004535809, 3}, // 2^21 * 479 + 1 {998244353, 3}, // 2^23 * 7 * 17 + 1 {985661441, 3}, // 2^22 * 5 * 47 + 1 {976224257, 3}, // 2^20 * 7^2 * 19 + 1 {975175681, 17}, // 2^21 * 3 * 5 * 31 + 1 {962592769, 7}, // 2^21 * 3^3 * 17 + 1 {950009857, 7}, // 2^21 * 4 * 151 + 1 {943718401, 7}, // 2^22 * 3^2 * 5^2 + 1 {935329793, 3}, // 2^22 * 223 + 1 {924844033, 5}, // 2^21 * 3^2 * 7^2 + 1 {469762049, 3}, // 2^26 * 7 + 1 {167772161, 3}, // 2^25 * 5 + 1 }; i64 extgcd(i64 a, i64 b, i64 &x, i64 &y) { i64 d; return b == 0 ? (x = 1, y = 0, a) : (d = extgcd(b, a % b, y, x), y -= a / b * x, d); } i64 modinv(i64 a, i64 mod) { i64 x, y; extgcd(a, mod, x, y); x %= mod; return x < 0 ? x + mod : x; } i64 modpow(i64 a, i64 b, i64 mod) { i64 r = 1; a %= mod; while(b) { if (b & 1) r = r * a % mod; a = a * a % mod; b >>= 1; } return r; } template struct Core { Core() { } using uint = uint_fast32_t; int MAX_H; vi64 zetaList, zetaInvList; explicit Core(int MAX_H) : MAX_H(MAX_H), zetaList(MAX_H), zetaInvList(MAX_H) { assert((mod & ((1 << MAX_H) - 1)) == 1); zetaList.back() = modpow(primitive, (mod - 1) / (1 << MAX_H), mod); zetaInvList.back() = modinv(zetaList.back(), mod); for (int ih = MAX_H - 2; ih >= 0; --ih) { zetaList[ih] = zetaList[ih + 1] * zetaList[ih + 1] % mod; zetaInvList[ih] = zetaInvList[ih + 1] * zetaInvList[ih + 1] % mod; } } void fft(vi64 &a, uint n, uint h, bool inv) const { static vi64 tmp; tmp.resize(n); uint mask = n - 1; for (uint i = n >> 1, ih = h - 1; i >= 1; i >>= 1, --ih) { i64 zeta = inv ? zetaInvList[h - 1 - ih] : zetaList[h - 1 - ih]; i64 powZeta = 1; for (uint j = 0; j < n; j += i) { for (uint k = 0; k < i; ++k) { tmp[j + k] = (a[((j << 1) & mask) + k] + powZeta * a[(((j << 1) + i) & mask) + k]) % mod; } powZeta = powZeta * zeta % mod; } swap(a, tmp); } if (inv) { i64 invN = modinv(n, mod); for (uint i = 0; i < n; ++i) a[i] = a[i] * invN % mod; } } vi64 conv(const vi64 &a, const vi64 &b) const { assert(a.size() + b.size() - 1 <= (1 << MAX_H)); if (a.size() == 0) return {}; if (b.size() == 0) return {}; return _conv(a, b); } vi64 _conv(vi64 a, vi64 b) const { uint deg = a.size() + b.size() - 1; uint h = 0, n = 1; while(n < deg) n <<= 1, ++h; a.resize(n), b.resize(n); return _convStrict(a, b, n, h); } vi64 _convStrict(vi64 a, vi64 b, uint n, uint h) const { fft(a, n, h, 0), fft(b, n, h, 0); for(uint i = 0; i < n; ++i) a[i] = a[i] * b[i] % mod; fft(a, n, h, 1); return a; } }; template void conv_for(int MAX_H, int n, int h, const vi64 &a, const vi64 &b, vi64 &mods, vi64 &coeffs, vvi64 &constants) { static const Core ntt(MAX_H); auto c = ntt._convStrict(a, b, n, h); mods[I] = NTT_PRIMES[I][0]; if(I >= 1) { conv_for(MAX_H, n, h, a, b, mods, coeffs, constants); } for(size_t i = 0; i < c.size(); ++i) { i64 v = (c[i] - constants[I][i]) * modinv(coeffs[I], mods[I]) % mods[I]; if(v < 0) v += mods[i]; for(size_t j = I + 1; j < mods.size(); ++j) { constants[j][i] = (constants[j][i] + coeffs[j] * v) % mods[j]; } } for(size_t j = I + 1; j < mods.size(); ++j) { coeffs[j] = (coeffs[j] * mods[I]) % mods[j]; } } template <> void conv_for< -1 >(int, int, int, const vector< i64 > &, const vector< i64 > &, vector< i64 > &, vector< i64 > &, vector< vector< i64 > > &) { } template vi64 conv( int MAX_H, vi64 a, vi64 b, i64 mod) { static_assert(USE >= 1, "USE must be positive"); static_assert(USE <= sizeof(NTT_PRIMES) / sizeof(*NTT_PRIMES), "USE is too big"); int deg = a.size() + b.size() - 1; int n = 1, h = 0; while(n < deg) n <<= 1, ++h; a.resize(n), b.resize(n); vi64 coeffs(USE + 1, 1); vvi64 constants(USE + 1, vi64(n, 0)); vi64 mods(USE + 1, mod); conv_for(MAX_H, n, h, a, b, mods, coeffs, constants); return constants.back(); } }//namespace NumberTheoreticTransform // BIT template struct BinaryIndexedTree { vector data; BinaryIndexedTree(int sz) { data.assign(++sz, 0); } T sum(int k) { T ret = 0; for(++k; k > 0; k -= k & -k) ret += data[k]; return ret; } void add(int k, T x) { for(++k; k < data.size(); k += k & -k) data[k] += x; } }; // セグ木 template struct SegmentTree { using F = function; int sz; vector seg; const F f; const Monoid M1; // n: 数列の数 // f: 求めたい関数(例えば最小値など)をラムダ式などで渡す // M1: 初期値 SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void set(int k, const Monoid &x) { seg[k+sz] = x; } void build() { for (int k = sz - 1; k > 0; k--) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } // xをkに更新する void update(int k, const Monoid &x) { k += sz; seg[k] = x; while(k >>= 1) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } // 第二引数の関数を適用する Monoid query(int a, int b) { Monoid L = M1, R = M1; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if(a & 1) L = f(L, seg[a++]); if(b & 1) R = f(seg[--b], R); } return f(L, R); } Monoid operator[](const int &k) const { return seg[k + sz]; } }; void Main(); int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); Main(); return 0; } void Main(){ //------------------------------------ int h, w, sx, sy, gx, gy; cin >> h >> w >> sy >> sx >> gy >> gx; sx--; sy--; gx--; gy--; string b[55]; bool used[55][55]; REP(i, h) cin >> b[i]; REP(i, 55) REP(j, 55) { used[i][j] = false; } queue q; q.push(mp(sy, sx)); used[sy][sx] = true; while (!q.empty()) { auto n = q.front(); q.pop(); if (n.first == gy && n.second == gx) break; int hh = b[n.first][n.second] - '0'; REP(i,4) { int ny = n.first + dy[i], nx = n.second + dx[i]; if (!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue; if (used[ny][nx]) continue; int nh = b[ny][nx] - '0'; if (abs(nh - hh) <= 1) { used[ny][nx] = true; q.push(mp(ny,nx)); } } REP(i,4) { int ny = n.first + 2 * dy[i], nx = n.second + 2 * dx[i]; if (!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue; if (used[ny][nx]) continue; int nh = b[ny][nx] - '0'; int ah = b[(ny + n.first) / 2][(nx + n.second) / 2] - '0'; if (hh - ah > 0 && nh == hh) { used[ny][nx] = true; q.push(mp(ny,nx)); } } } if (used[gy][gx]) cout << "YES" << endl; else cout << "NO" << endl; //------------------------------------ }