結果

問題 No.424 立体迷路
ユーザー T101010101T101010101
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 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<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)
// xroot , 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0