結果
問題 | No.424 立体迷路 |
ユーザー | kapo |
提出日時 | 2016-09-22 23:40:56 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,385 bytes |
コンパイル時間 | 578 ms |
コンパイル使用メモリ | 85,468 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 07:06:31 |
合計ジャッジ時間 | 1,273 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 1 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 1 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 1 ms
5,376 KB |
testcase_22 | AC | 1 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 1 ms
5,376 KB |
testcase_25 | AC | 1 ms
5,376 KB |
ソースコード
#define _CRT_SECURE_NO_WARNINGS // #pragma warning(disable:4996) #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <string> #include <queue> #include <functional> #include <sstream> #include <cmath> #include <set> #include <map> #include <stack> using namespace std; #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(a);i>=(b);i--) #define pb push_back #define mp(a,b) make_pair(a,b) #define all(a) a.begin(),a.end() #define len(x) ((int)(x).size()) #define tmax(a,b,c) max((a),max((b),(c))) #define tmin(a,b,c) min((a),min((b),(c))) #define debug(x) cerr << #x << " is " << x << endl; #define debug2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl; #define debuga(g,h,w) rep(i,0,h) { rep(j,0,w) cout << g[i][j] << " "; cout << endl;} #define debugv(v) for(auto&& x : v){cout << x << " ";} cout << endl; typedef pair<int, int> Pii; typedef map<int, int> Mii; typedef vector<int> Vi; typedef vector<vector<int> > VVi; typedef long long ll; const int inf = 2e9; const ll ll_inf = 1e17; const int mod = 1e9 + 7; const long double eps = 1e-10; typedef pair<ll, ll> Pll; int h, w; int sx, sy, gx, gy; int g[51][51]; int dx[4] = {0,1,0,-1}; // nesw int dy[4] = {1,0,-1,0}; int used[51][51]; int main() { cin >> h >> w; cin >> sy >> sx >> gy >> gx; sx--; sy--; gx--; gy--; rep(i,0,h) rep(j,0,w) { char c; cin >> c; g[i][j] = (int)(c - '0'); } //debuga(g,h,w); queue<Pii> que; que.push(mp(sy,sx)); used[sy][sx] = true; while (!que.empty()) { Pii p = que.front(); que.pop(); int by = p.first, bx = p.second; if (bx == gx && by == gy) { cout << "YES" << endl; return 0; } int height = g[by][bx]; //printf("height=%d by=%d bx=%d\n",height,by,bx); rep(i,0,4) { int nx = bx + dx[i]; int ny = by + dy[i]; if (nx < 0 || ny < 0 || nx >= w || ny >= h) continue; if (used[ny][nx]) continue; int t = g[ny][nx]; if (height-1 <= t && t <= height+1) { que.push(mp(ny,nx)); used[ny][nx] = true; } } rep(i,0,4) { int nx = bx + dx[i] + dx[i]; int ny = by + dy[i] + dy[i]; if (nx < 0 || ny < 0 || nx >= w || ny >= h) continue; if (used[ny][nx]) continue; int t = g[ny][nx]; if (t == height && g[by+dy[i]][bx+dx[i]] < t) { que.push(mp(ny,nx)); used[ny][nx] = true; } } } cout << "NO" << endl; return 0; }