#pragma region Macros #include using namespace std; using namespace __gnu_pbds; // using namespace __gnu_cxx; #define TO_STRING(var) # var #define pb emplace_back #define int ll #define endl '\n' using ll = long long; using ld = long double; const ld PI = acos(-1); const ld EPS = 1e-10; const int INF = 1 << 30; const ll INFL = 1LL << 62; // const int MOD = 998244353; const int MOD = 1000000007; int ceil(int x, int y) {return (x > 0 ? (x + y - 1) / y : x / y);} int POW(int x, int y) { if (y != (int)(y) or y < 0 or x != 0 && x != 1 && y > 64) {cout << "Error" << endl;return 0;} if (y == 0) return 1; if (y % 2 == 0) return POW(x * x, y / 2); return x * POW(x, y - 1); } __attribute__((constructor)) void constructor() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); } #pragma endregion class UnionFind { public: UnionFind() = default; UnionFind(int n) : par(n), // max_node(n), TODO // min_node(n), TODO sz(n, 1) { iota(par.begin(), par.end(), 0); } // https://algo-method.com/tasks/561 // UnionFind(int n, const vector& V) : par(n), sum(V), // sz(n, 1) { iota(par.begin(), par.end(), 0); } int root(int x) { if (par[x] == x) return x; return (par[x] = root(par[x])); } bool unite(int x, int y) { int rx = root(x); int ry = root(y); if (rx == ry) return false; // union by size (小さいほうが子になる) if (sz[rx] < sz[ry]) swap(rx, ry); sz[rx] += sz[ry]; par[ry] = rx; // sum[rx] += sum[ry]; // max_node[rx] = max(max_node[rx], max_node[ry]); // min_node[rx] = min(min_node[rx], min_node[ry]); return true; } bool issame(int x, int y) { return (root(x) == root(y)); } // xが属するグループの要素数を返す int size(int x) { return sz[root(x)]; } // xが属するグループの{重さ}の合計値 int get_sum(int x) { return sum[root(x)]; } // xを含む根付き木の中での頂点番号の最大値 // int get_max(int x) { // return max_node[root(x)]; // } // xを含む根付き木の中での頂点番号の最小値 // int get_min(int x) { // return min_node[root(x)]; // } // 各素集合ごとに分割。G[i](0 <= i < K)の隣接リスト vector> groups(int n) { vector> G(n); for (int x = 0; x < n; x++) { G[root(x)].push_back(x); } G.erase( remove_if(G.begin(), G.end(), [&](const vector& v) { return v.empty(); }), G.end()); return G; } private: // rootの場合は自身が親 vector par; // グループの要素数(root用) // xがroot のときのみ, sz[x] はそのグループに属する要素数を表す vector sz; // 渡された配列の合計値 vector sum; // 集合内の最大の頂点番号と最小の頂点番号 vector max_node; vector min_node; }; const vector dx = {1, 0, -1, 0}; const vector dy = {0, -1, 0, 1}; const vector dx2 = {0, 0, 2, -2}; const vector dy2 = {2, -2, 0, 0}; int H, W, sx, sy, gx, gy; bool isvalid(int x, int y) { if(x >= 0 && x < H && y >= 0 && y < W) return true; else return false; } int getnum(int x, int y) { return (x * W + y); } signed main(){ cin >> H >> W >> sx >> sy >> gx >> gy; sx--; sy--; gx--; gy--; vector> B(H, vector(W)); for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { char c; cin >> c; B[i][j] = c - '0'; } } queue> qu; qu.emplace(sx, sy); UnionFind uf(H * W + 1); while (!qu.empty()) { auto p = qu.front(); qu.pop(); for (int k = 0; k < 4; k++) { int ni = p.first + dx[k]; int nj = p.second + dy[k]; if (isvalid(ni, nj) == false) continue; if (uf.issame(getnum(p.first, p.second), getnum(ni, nj))) continue; if (abs(B[p.first][p.second] - B[ni][nj]) > 1) continue; uf.unite(getnum(p.first, p.second), getnum(ni, nj)); qu.emplace(ni, nj); } for (int k = 0; k < 4; k++) { int ni = p.first + dx2[k]; int nj = p.second + dy2[k]; if (isvalid(ni, nj) == false) continue; if (uf.issame(getnum(p.first, p.second), getnum(ni, nj))) continue; if (B[p.first][p.second] != B[ni][nj]) continue; if (B[p.first][p.second] < B[p.first + dx2[k] / 2][p.second+ dy2[k] / 2]) continue; uf.unite(getnum(p.first, p.second), getnum(ni, nj)); qu.emplace(ni, nj); } } if (uf.issame(getnum(sx, sy), getnum(gx, gy))) cout << "YES" << endl; else cout << "NO" << endl; }