結果
問題 | 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_ENVIRONMENTtemplate <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;}