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

• 問題: No.3504 Insert Maze
• ユーザー: irinoirino
• 提出日時: 2026-03-02 22:43:57
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 32 ms / 2,000 ms
• コード長: 3,451 bytes
• コンパイル時間: 1,729 ms
• コンパイル使用メモリ: 176,784 KB
• 実行使用メモリ: 8,832 KB
• 最終ジャッジ日時: 2026-04-17 19:30:40
• 合計ジャッジ時間: 9,463 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

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

ソースコード

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

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

    int H, W;
    cin >> H >> W;

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

    auto passable = [&](int i, int j) -> bool {
        return g[i][j] == '.' || g[i][j] == 'S' || g[i][j] == 'G';
    };

    // fwd[i][j] : (0,0) から右・下移動のみで (i,j) に到達可能か
    vector<vector<bool>> fwd(H, vector<bool>(W, false));
    fwd[0][0] = true;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (!fwd[i][j]) continue;
            if (j + 1 < W && passable(i, j + 1)) fwd[i][j + 1] = true;
            if (i + 1 < H && passable(i + 1, j)) fwd[i + 1][j] = true;
        }
    }

    // rev[i][j] : (i,j) から右・下移動のみで G=(H-1,W-1) に到達可能か
    // (G から左・上への逆伝搬で求める)
    vector<vector<bool>> rev(H, vector<bool>(W, false));
    rev[H - 1][W - 1] = true;
    for (int i = H - 1; i >= 0; i--) {
        for (int j = W - 1; j >= 0; j--) {
            if (!rev[i][j]) continue;
            if (j - 1 >= 0 && passable(i, j - 1)) rev[i][j - 1] = true;
            if (i - 1 >= 0 && passable(i - 1, j)) rev[i - 1][j] = true;
        }
    }

    // ---- 超能力 0 回 ----
    if (fwd[H - 1][W - 1]) {
        cout << H + W - 2 << '\n';
        return 0;
    }

    // ---- 超能力 1 回 ----
    // 列挿入: 列 c と c+1 の間に '.' 列を挿入 (c : 0-indexed, 0..W-2)
    //   "列 c に到達できた最小行" min_r 以降の行で、元の列 c+1 が passable かつ rev = true なら OK
    {
        // 各列 c について min_row_fwd[c] = min{i : fwd[i][c]=1} (なければ H)
        vector<int> min_row_fwd(W, H);
        for (int j = 0; j < W; j++) {
            for (int i = 0; i < H; i++) {
                if (fwd[i][j]) { min_row_fwd[j] = i; break; }
            }
        }

        for (int c = 0; c + 1 < W; c++) {
            if (min_row_fwd[c] == H) continue; // 列 c に未到達
            // 列 c+1 の suffix: suf[i] = (i 以降に passable && rev の行が存在するか)
            bool suf = false;
            for (int i = H - 1; i >= min_row_fwd[c]; i--) {
                if (passable(i, c + 1) && rev[i][c + 1]) { suf = true; break; }
            }
            if (suf) {
                cout << H + W - 1 << '\n';
                return 0;
            }
        }
    }

    // 行挿入: 行 r と r+1 の間に '.' 行を挿入 (r : 0-indexed, 0..H-2)
    //   "行 r に到達できた最小列" min_c 以降の列で、元の行 r+1 が passable かつ rev = true なら OK
    {
        vector<int> min_col_fwd(H, W);
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (fwd[i][j]) { min_col_fwd[i] = j; break; }
            }
        }

        for (int r = 0; r + 1 < H; r++) {
            if (min_col_fwd[r] == W) continue; // 行 r に未到達
            bool suf = false;
            for (int j = W - 1; j >= min_col_fwd[r]; j--) {
                if (passable(r + 1, j) && rev[r + 1][j]) { suf = true; break; }
            }
            if (suf) {
                cout << H + W - 1 << '\n';
                return 0;
            }
        }
    }

    // ---- 超能力 2 回 (常に到達可能) ----
    cout << H + W << '\n';
    return 0;
}