結果
問題 |
No.424 立体迷路
|
ユーザー |
|
提出日時 | 2019-08-06 11:13:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,343 bytes |
コンパイル時間 | 826 ms |
コンパイル使用メモリ | 94,540 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-18 13:52:08 |
合計ジャッジ時間 | 1,580 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
#include <iostream> #include <vector> #include <utility> #include <set> #include <list> #include <cassert> #include <queue> #include <cmath> using namespace std; using ll = long long int; #define REP(i, n) for(int i = 0; i < (int)(n); i++) #define YES(n) std::cout << ((n) ? "YES" : "NO" ) << "\n"; #define Yes(n) std::cout << ((n) ? "Yes" : "No" ) << "\n"; #define ALL_INCLUDED_ENVIRONMENT template <class T, class Alloc, template <class, class> class C> std::ostream& operator<<(std::ostream& o, const C<T, Alloc>& v) { o << "{"; bool init = 1; for (auto e : v) { if (init) { init = 0; } else { o << ", "; } o << e; } o << "}"; return o; } template <class X, class Y> std::ostream& operator<<(std::ostream& o, const std::pair<X, Y>& p) { o << "(" << p.first << ", " << p.second << ")"; return o; } ll h, w, sx, sy, gx, gy; vector<vector<ll> > bs; queue<pair<ll, ll>> que; vector<vector<bool> > visited; void step(ll x, ll y, ll newx, ll newy) { if (newx >= 0 && newx < h && newy >= 0 && newy < w && abs(bs[x][y] - bs[newx][newy]) <= 1 && visited[newx][newy] == 0) { visited[newx][newy] = 1; que.push(make_pair(newx, newy)); } } void jump(ll x, ll y, ll newx, ll newy) { ll midx = (x + newx)/2; ll midy = (y + newy)/2; if (newx >= 0 && newx < h && newy >= 0 && newy < w && bs[x][y] == bs[newx][newy] && bs[midx][midy] < bs[x][y] && visited[newx][newy] == 0) { visited[newx][newy] = 1; que.push(make_pair(newx, newy)); } } int main() { // cin.tie(0); // ios::sync_with_stdio(false); cin >> h >> w >> sx >> sy >> gx >> gy; cin.ignore(); sx--; sy--; gx--; gy--; bs = vector<vector<ll> >(h, vector<ll>(w, 0)); visited = vector<vector<bool> >(h, vector<bool>(w, 0)); visited[sx][sy] = 1; que.push(make_pair(sx, sy)); string line; REP (i, h) { getline(cin, line); REP (j, w) { assert('0' <= line[j] && line[j] <= '9'); bs[i][j] = line[j]-'0'; } } while (!que.empty()) { pair<ll, ll> node = que.front(); ll x = node.first; ll y = node.second; que.pop(); step(x, y, x-1, y); step(x, y, x+1, y); step(x, y, x, y-1); step(x, y, x, y+1); jump(x, y, x-2, y); jump(x, y, x+2, y); jump(x, y, x, y-2); jump(x, y, x, y+2); } YES(visited[gx][gy]); return 0; }