#119502 (C++14) No.424 立体迷路

• 問題: No.424 立体迷路
• ユーザー: ant2357
• 提出日時: 2016-09-25 17:58:37
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 3 ms / 2,000 ms
• コード長: 2,290 bytes
• コンパイル時間: 2,067 ms
• コンパイル使用メモリ: 183,960 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-07-05 07:10:06
• 合計ジャッジ時間: 2,928 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	AC * 5
other	AC * 21

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include "bits/stdc++.h"
#include <unordered_set>
#define _CRT_SECURE_NO_WARNINGS
#define REP(i, n) for(decltype(n) i = 0; i < (n); i++)
#define REP2(i, x, n) for(decltype(x) i = (x); i < (n); i++)
#define REP3(i, x, n) for(decltype(x) i = (x); i <= (n); i++)
#define RREP(i, n) for (decltype(n) i = (n) - 1; i >= 0; i--)
#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())
using namespace std;
const int dy[] = { 0, 1, 0, -1 };
const int dx[] = { 1, 0, -1, 0 };
using LL = long long int;
using LD = long double;
const int INF = (1 << 30) - 1;
const LL INF64 = ((LL)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;
using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<LL>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vs = vector<string>;
using vb = vector<bool>;
//==============================================
int h, w, sy, sx, gy, gx;
vs M;
vector<vb>D;
bool bfs() {
    queue<pii> coord;
    coord.push(make_pair(sy, sx));
    D[sy][sx] = true;
    while (!coord.empty()) {
        pii now = coord.front(); coord.pop();
        const int y = now.first;
        const int x = now.second;
        const int nowH = M[y][x] - '0';
        if (gy == y && gx == x) return true;
        int ny, nx;
        REP(i, 4) {
            ny = y + dy[i];
            nx = x + dx[i];
            if (nx < 0 || w <= nx || ny < 0 || h <= ny) continue;
            if (D[ny][nx]) continue;
            if (abs(nowH - (M[ny][nx] - '0')) > 1) continue;
            D[ny][nx] = true;
            coord.push(make_pair(ny, nx));
        }
        REP(i, 4) {
            ny = y + dy[i] * 2;
            nx = x + dx[i] * 2;
            if (nx < 0 || w <= nx || ny < 0 || h <= ny) continue;
            if (D[ny][nx]) continue;
            const int ly = y + dy[i];
            const int lx = x + dx[i];
            if (nowH < M[ly][lx] - '0') continue;
            if (nowH != M[ny][nx] - '0') continue;
            D[ny][nx] = true;
            coord.push(make_pair(ny, nx));
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> h >> w >> sy >> sx >> gy >> gx;
    M.resize(h);
    D.resize(h, vb(w));
    sy--; sx--; gy--; gx--;
    REP(i, h) cin >> M[i];
    cout << (bfs() ? "YES\n" : "NO\n");
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX