結果

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

ソースコード

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

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0