結果
問題 | No.424 立体迷路 |
ユーザー |
|
提出日時 | 2022-12-07 19:53:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 4,837 bytes |
コンパイル時間 | 3,886 ms |
コンパイル使用メモリ | 263,108 KB |
最終ジャッジ日時 | 2025-02-09 06:15:29 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
#pragma region Macros#include <bits/extc++.h>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 endregionclass UnionFind {public:UnionFind() = default;UnionFind(int n) : par(n),// max_node(n), TODO// min_node(n), TODOsz(n, 1) { iota(par.begin(), par.end(), 0); }// https://algo-method.com/tasks/561// UnionFind(int n, const vector<int>& 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<vector<int>> groups(int n) {vector<vector<int>> 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<int>& v) { return v.empty(); }),G.end());return G;}private:// rootの場合は自身が親vector<int> par;// グループの要素数(root用)// xがroot のときのみ, sz[x] はそのグループに属する要素数を表すvector<int> sz;// 渡された配列の合計値vector<int> sum;// 集合内の最大の頂点番号と最小の頂点番号vector<int> max_node;vector<int> min_node;};const vector<int> dx = {1, 0, -1, 0};const vector<int> dy = {0, -1, 0, 1};const vector<int> dx2 = {0, 0, 2, -2};const vector<int> 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<vector<int>> B(H, vector<int>(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<pair<int,int>> 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;}