結果

問題 No.424 立体迷路
ユーザー yosupotyosupot
提出日時 2016-09-22 23:44:48
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,309 bytes
コンパイル時間 766 ms
コンパイル使用メモリ 101,492 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 07:06:33
合計ジャッジ時間 1,372 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T = ll> constexpr T TEN(int n) {return (n==0)?1:10*TEN<T>(n-1);}
int bsr(int x) { return 31 - __builtin_clz(x); }

const int MN = 52;
int g[MN][MN];
bool ok[MN][MN];
const int d4[4][2] = {
    {1, 0},
    {0, 1},
    {-1, 0},
    {0, -1},
};

int main() {
    int h, w;
    cin >> h >> w;
    int sy, sx, gy, gx;
    cin >> sy >> sx >> gy >> gx;
    sy--; sx--; gy--; gx--;
    for (int i = 0; i < h; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < w; j++) {
            g[i][j] = s[j]-'0';
        }
    }
    auto bc = [&](int x, int y) {
        return (0 <= x && x < w && 0 <= y && y < h);
    };
    ok[sy][sx] = true;
    while (true) {
        bool update = false;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (!ok[i][j]) continue;
                for (int d = 0; d < 4; d++) {
                    int ni = i+2*d4[d][0];
                    int nj = j+2*d4[d][1];
                    int mi = (ni+i)/2;
                    int mj = (nj+j)/2;
                    if (bc(nj, ni) && g[ni][nj] == g[i][j] && g[mi][mj] < g[i][j]) {
                        if (!ok[ni][nj]) {
                            update = true;
                            ok[ni][nj] = true;
                        }
                    }
                }
                for (int d = 0; d < 4; d++) {
                    int ni = i+d4[d][0];
                    int nj = j+d4[d][1];
                    if (bc(nj, ni) && abs(g[ni][nj] - g[i][j]) <= 1) {
                        if (!ok[ni][nj]) {
                            update = true;
                            ok[ni][nj] = true;
                        }
                    }
                }                
            }
        }
        if (!update) break;
    }
    if (ok[gy][gx]) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
    return 0;
}
0