#1152731 (C++23) No.3504 Insert Maze

• 問題: No.3504 Insert Maze
• ユーザー: Naru820
• 提出日時: 2026-03-17 21:52:42
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 818 ms / 2,000 ms
• コード長: 3,305 bytes
• コンパイル時間: 1,521 ms
• コンパイル使用メモリ: 166,300 KB
• 実行使用メモリ: 132,736 KB
• 最終ジャッジ日時: 2026-04-17 19:41:25
• 合計ジャッジ時間: 35,102 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

ファイルパターン	結果
sample	AC * 3
other	AC * 85

ソースコード

// gemini 3.1pro
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    // 4つの状態 × H × W の最大ノード数
    int max_nodes = 4 * H * W;
    // 距離配列（-1で未訪問を管理）
    vector<int> dist(max_nodes, -1);
    // 高速なキュー（vectorで代用）
    vector<int> q(max_nodes);
    int head = 0, tail = 0;

    // 次の状態をキューに追加するラムダ式
    auto push = [&](int d, int ntype, int nr, int nc) {
        // 範囲外チェック
        if (nr < 0 || nc < 0) return;
        if (ntype == 0 && (nr >= H || nc >= W)) return;
        if (ntype == 1 && (nr >= H - 1 || nc >= W)) return;
        if (ntype == 2 && (nr >= H || nc >= W - 1)) return;
        if (ntype == 3 && (nr >= H - 1 || nc >= W - 1)) return;
        
        // 通常状態の場合は壁をチェック
        if (ntype == 0 && grid[nr][nc] == '#') return;
        
        int v = ntype * H * W + nr * W + nc;
        if (dist[v] == -1) {
            dist[v] = d + 1;
            q[tail++] = v;
        }
    };

    // スタート地点 (タイプ0, 0行目, 0列目)
    int start_id = 0 * H * W + 0 * W + 0;
    dist[start_id] = 0;
    q[tail++] = start_id;

    while (head < tail) {
        int u = q[head++];
        int type = u / (H * W);
        int rem = u % (H * W);
        int r = rem / W;
        int c = rem % W;
        int d = dist[u];

        if (type == 0) { // EE (通常マス)
            if (r == H - 1 && c == W - 1) {
                cout << d << "\n";
                return 0;
            }
            // そのまま移動
            push(d, 0, r + 1, c);
            push(d, 0, r - 1, c);
            push(d, 0, r, c + 1);
            push(d, 0, r, c - 1);
            // 横ハイウェイ(OE)へ降りる
            push(d, 1, r, c);
            push(d, 1, r - 1, c);
            // 縦ハイウェイ(EO)へ降りる
            push(d, 2, r, c);
            push(d, 2, r, c - 1);
        } else if (type == 1) { // OE (横ハイウェイ)
            // 通常マスへ戻る
            push(d, 0, r, c);
            push(d, 0, r + 1, c);
            // ハイウェイ上を横移動
            push(d, 1, r, c - 1);
            push(d, 1, r, c + 1);
            // 交差点(OO)へ移動
            push(d, 3, r, c);
            push(d, 3, r, c - 1);
        } else if (type == 2) { // EO (縦ハイウェイ)
            // 通常マスへ戻る
            push(d, 0, r, c);
            push(d, 0, r, c + 1);
            // ハイウェイ上を縦移動
            push(d, 2, r - 1, c);
            push(d, 2, r + 1, c);
            // 交差点(OO)へ移動
            push(d, 3, r, c);
            push(d, 3, r - 1, c);
        } else if (type == 3) { // OO (交差点)
            // ハイウェイへ抜ける
            push(d, 1, r, c);
            push(d, 1, r, c + 1);
            push(d, 2, r, c);
            push(d, 2, r + 1, c);
        }
    }

    // どうやっても到達できない場合
    cout << -1 << "\n";
    return 0;
}