結果
問題 | No.424 立体迷路 |
ユーザー |
![]() |
提出日時 | 2016-09-22 22:30:55 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,339 bytes |
コンパイル時間 | 1,491 ms |
コンパイル使用メモリ | 163,448 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-05 06:59:00 |
合計ジャッジ時間 | 2,054 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h>using namespace std;struct UnionFind{vector< int > data;UnionFind(int sz){data.assign(sz, -1);}void unite(int x, int y){x = find(x), y = find(y);if(x != y) {if(data[x] > data[y]) swap(x, y);data[x] += data[y];data[y] = x;}}int find(int k){if(data[k] < 0) return (k);return (data[k] = find(data[k]));}int size(int k){return (-data[find(k)]);}};int main(){int H, W;int sx, sy, gx, gy;string b[50];cin >> H >> W;cin >> sy >> sx >> gy >> gx;for(int i = 0; i < H; i++) {cin >> b[i];}--sx, --sy, --gx, --gy;UnionFind tree(H * W);for(int i = 0; i < H; i++) {for(int j = 0; j < W; j++) {if(j > 0 && abs(b[i][j - 1] - b[i][j]) <= 1) tree.unite(i * W + j, i * W + j - 1);if(i > 0 && abs(b[i - 1][j] - b[i][j]) <= 1) tree.unite(i * W + j, i * W + j - W);if(j > 1 && b[i][j - 2] == b[i][j] && b[i][j - 2] > b[i][j - 1] && b[i][j] > b[i][j - 1]) tree.unite(i * W + j, i * W + j - 2);if(i > 1 && b[i - 2][j] == b[i][j] && b[i - 2][j] > b[i - 1][j] && b[i][j] > b[i - 1][j]) tree.unite(i * W + j, i * W + j - W - W);}}if(tree.find(sy * W + sx) == tree.find(gy * W + gx)) {cout << "YES" << endl;} else {cout << "NO" << endl;}}