結果

問題 No.3504 Insert Maze
コンテスト
ユーザー よいちなすの
提出日時 2026-04-18 04:20:54
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 646 ms / 2,000 ms
コード長 3,602 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,732 ms
コンパイル使用メモリ 339,792 KB
実行使用メモリ 132,608 KB
最終ジャッジ日時 2026-04-18 04:21:28
合計ジャッジ時間 30,009 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    for (int i = 0; i < H; ++i) cin >> grid[i];

    long long HW = (long long)H * W;
    vector<int> dist(4 * HW, -1);
    vector<int> q;
    q.reserve(4 * HW);

    dist[0] = 0;
    q.push_back(0);
    int head = 0;

    while (head < q.size()) {
        int curr = q[head++];
        int d = dist[curr];
        int p = curr / HW;
        int rem = curr % HW;
        int r = rem / W;
        int c = rem % W;

        if (p == 0) {
            int dr[] = {0, 0, 1, -1}, dc[] = {1, -1, 0, 0};
            for (int i = 0; i < 4; ++i) {
                int nr = r + dr[i], nc = c + dc[i];
                if (nr >= 0 && nr < H && nc >= 0 && nc < W && grid[nr][nc] != '#') {
                    int nxt = nr * W + nc;
                    if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); }
                }
            }
            if (r < H - 1) { int nxt = 1 * HW + r * W + c; if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
            if (r > 0) { int nxt = 1 * HW + (r - 1) * W + c; if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
            if (c < W - 1) { int nxt = 2 * HW + r * W + c; if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
            if (c > 0) { int nxt = 2 * HW + r * W + (c - 1); if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
        } else if (p == 1) {
            if (c > 0) { int nxt = 1 * HW + r * W + (c - 1); if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
            if (c < W - 1) { int nxt = 1 * HW + r * W + (c + 1); if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
            if (grid[r][c] != '#') { int nxt = r * W + c; if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
            if (grid[r + 1][c] != '#') { int nxt = (r + 1) * W + c; if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
            if (c < W - 1) { int nxt = 3 * HW + r * W + c; if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
            if (c > 0) { int nxt = 3 * HW + r * W + (c - 1); if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
        } else if (p == 2) {
            if (r > 0) { int nxt = 2 * HW + (r - 1) * W + c; if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
            if (r < H - 1) { int nxt = 2 * HW + (r + 1) * W + c; if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
            if (grid[r][c] != '#') { int nxt = r * W + c; if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
            if (grid[r][c + 1] != '#') { int nxt = r * W + (c + 1); if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
            if (r < H - 1) { int nxt = 3 * HW + r * W + c; if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
            if (r > 0) { int nxt = 3 * HW + (r - 1) * W + c; if (dist[nxt] == -1) { dist[nxt] = d + 1; q.push_back(nxt); } }
        } else {
            int n1 = 1 * HW + r * W + c, n2 = 1 * HW + r * W + (c + 1);
            int n3 = 2 * HW + r * W + c, n4 = 2 * HW + (r + 1) * W + c;
            if (dist[n1] == -1) { dist[n1] = d + 1; q.push_back(n1); }
            if (dist[n2] == -1) { dist[n2] = d + 1; q.push_back(n2); }
            if (dist[n3] == -1) { dist[n3] = d + 1; q.push_back(n3); }
            if (dist[n4] == -1) { dist[n4] = d + 1; q.push_back(n4); }
        }
    }

    cout << dist[(H - 1) * W + (W - 1)] << endl;
    return 0;
}
0