結果
問題 | No.424 立体迷路 |
ユーザー |
![]() |
提出日時 | 2019-09-10 18:13:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,154 bytes |
コンパイル時間 | 1,787 ms |
コンパイル使用メモリ | 172,656 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-02 16:17:58 |
合計ジャッジ時間 | 2,764 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define REP(i,a) for(int i = 0; i < (a); i++)#define ALL(a) (a).begin(),(a).end()typedef long long ll;typedef pair<int, int> P;const int INF = 1e9;const int MOD = 1e9 + 7;struct UnionFind{vector<int> par;vector<int> siz;UnionFind(int n){init(n);}//n要素で初期化void init(int n){par.resize(n);siz.resize(n);for(int i = 0; i < n; i++){par[i] = i;siz[i] = 1;}}//木の根を求めるint root(int x){if(par[x] == x) return x;else return par[x] = root(par[x]);}//xとyの属する集合を併合void unite(int x, int y){x = root(x);y = root(y);if(x == y) return;if(siz[x] < siz[y]) swap(x, y);siz[x] += siz[y];par[y] = x;}bool same(int x, int y){return root(x) == root(y);}int size(int x){return siz[root(x)];}};int dx[2] = {1, 0}, dy[2] = {0, 1};signed main(){int h,w,sx,sy,gx,gy;cin >> h >> w;cin >> sx >> sy >> gx >> gy;sx--;sy--;gx--;gy--;string b[h];REP(i,h){cin >> b[i];}int c[h][w];REP(i,h){REP(j,w){c[i][j] = b[i][j] - '0';}}int cnt = 0;int n[h][w];REP(i,h){REP(j,w){n[i][j] = cnt;cnt++;}}UnionFind uf(cnt);REP(i,h){REP(j,w){REP(k,2){if(i + dx[k] < h && j + dy[k] < w && c[i][j] - 1 <= c[i + dx[k]][j + dy[k]] && c[i + dx[k]][j + dy[k]] <= c[i][j] + 1){uf.unite(n[i][j], n[i + dx[k]][j + dy[k]]);}if(i + 2 * dx[k] < h && j + 2 * dy[k] < w && c[i][j] == c[i + 2 * dx[k]][j + 2 * dy[k]] && c[i + dx[k]][j + dy[k]] < c[i][j]){uf.unite(n[i][j], n[i + 2 * dx[k]][j + 2 * dy[k]]);}}}}if(uf.same(n[sx][sy], n[gx][gy])){cout << "YES" << endl;}else{cout << "NO" << endl;}}