結果
問題 | No.424 立体迷路 |
ユーザー |
![]() |
提出日時 | 2022-01-29 19:26:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,849 bytes |
コンパイル時間 | 2,378 ms |
コンパイル使用メモリ | 204,540 KB |
最終ジャッジ日時 | 2025-01-27 17:53:06 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using P = pair<int, int>;using T = tuple<int, int, int>;#define al(a) a.begin(), a.end()#define ral(a) a.rbegin(), a.rend()#define sz(a) (int)a.size()#define rep(i, n) for (int i = 0; i < (n); ++i)#define rrep(i, n) for (int i = 1; i <= (n); ++i)#define drep(i, n) for (int i = (n)-1; i >= 0; --i)#define db(a, b) cout << #a << ": " << a << " " << #b << ": " << b << endl;//{上,右,下,左}const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};int main() {int h, w;cin >> h >> w;int sx, sy, tx, ty;cin >> sx >> sy >> tx >> ty;--sx, --sy, --tx, --ty;vector<string> s(h);rep(i, h) cin >> s[i];queue<P> q;const int INF = 1001001001;vector dist(h, vector<int>(w, INF));auto push = [&](int nx, int ny, int nd) {if (nx < 0 || ny < 0 || nx >= h || ny >= w) return;if (dist[nx][ny] != INF) return;dist[nx][ny] = nd;q.emplace(nx, ny);};push(sx, sy, 0);while (sz(q)) {auto [x, y] = q.front();int high = s[x][y] - '0';int d = dist[x][y];q.pop();rep(i, 4) {{int nx = dx[i] + x, ny = dy[i] + y;if (nx >= 0 && ny >= 0 && nx < h && ny < w) {int nh = s[nx][ny] - '0';if (high == nh || high + 1 == nh || high - 1 == nh)push(nx, ny, d + 1);}}{int nx = dx[i] * 2 + x, ny = dy[i] * 2 + y;int cx = dx[i] + x, cy = dy[i] + y;if (nx >= 0 && ny >= 0 && nx < h && ny < w) {// db(nx, ny);// db((nx < h), h);int nh = s[nx][ny] - '0';int ch = s[cx][cy] - '0';if (high == nh && high > ch) push(nx, ny, d + 1);}}}}if (dist[tx][ty] != INF)cout << "YES" << endl;elsecout << "NO" << endl;return 0;}