結果

問題 No.424 立体迷路
コンテスト
ユーザー kichirb3
提出日時 2018-03-20 13:14:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,641 bytes
コンパイル時間 1,024 ms
コンパイル使用メモリ 86,784 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 07:15:36
合計ジャッジ時間 1,721 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

// No.424 立体迷路
// https://yukicoder.me/problems/no/424
//

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

string solve(vector<vector<int>> &maze, int sx, int sy, int gx, int gy, int h, int w);


int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int h, w;
    cin >> h >> w;
    int sx, sy, gx, gy;
    cin >> sy >> sx >> gy >> gx;

    vector<vector<int>> maze(h);
    for (auto y = 0; y < h; ++y)
        maze[y].resize(w);

    for (auto y = 0; y < h; ++y) {
        for (auto x = 0; x < w; ++x) {
            char c;
            cin >> c;
            maze[y][x] = c - '0';
        }
    }
    string ans = solve(maze, sx-1, sy-1, gx-1, gy-1, h, w);
    cout << ans << endl;
}

struct pos {
    int x;
    int y;
};

string solve(vector<vector<int>> &maze, int sx, int sy, int gx, int gy, int h, int w) {
    vector<int> dx = {0, 0, -1, 1};
    vector<int> dy = {-1, 1, 0, 0};

    vector<int> dx2 = {0, 0, -2, 2};
    vector<int> dy2 = {-2, 2, 0, 0};

    vector<vector<bool>> explored(h);
    for (auto y = 0; y < h; ++y) {
        explored[y].resize(w);
        for (auto x = 0; x < w; ++x)
            explored[y][x] = false;
    }
    deque<pos> Q;
    Q.push_back(pos{sx, sy});
    while (!Q.empty()) {
        pos c = Q.front();
        Q.pop_front();
        int ch = maze[c.y][c.x];

        // 隣りの同じ高さのブロックに歩いて移動 または 隣りの±1の高さのブロックにはしごをかけて移動
        for (int i = 0; i < dx.size(); ++i) {
            pos n {c.x + dx[i], c.y + dy[i]};
            if (n.x >= 0 && n.x < w && n.y >= 0 && n.y < h && explored[n.y][n.x] == false) {
                int nh = maze[n.y][n.x];
                if (nh >= ch-1 && nh <= ch+1) {
                    if (n.x == gx && n.y == gy)
                        return "YES";
                    Q.push_back(n);
                    explored[n.y][n.x] = true;
                }
            }
        }
        // 2ブロック先の同じ高さのマスにはしごを渡して移動
        for (int i = 0; i < dx.size(); ++i) {
            pos n {c.x + dx2[i], c.y + dy2[i]};
            if (n.x >= 0 && n.x < w && n.y >= 0 && n.y < h && explored[n.y][n.x] == false) {
                int nh = maze[n.y][n.x];
                int mh = maze[(n.y+c.y)/2][(n.x+c.x)/2];
                if (nh == ch && mh <= ch) {
                    if (n.x == gx && n.y == gy)
                        return "YES";
                    Q.push_back(n);
                    explored[n.y][n.x] = true;
                }
            }
        }
    }
    return "NO";
}
0