結果

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

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

int main() {
    ll H, W;
    cin >> H >> W;

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

    S[0][0] = '.';
    S[H - 1][W - 1] = '.';
    queue<tuple<ll, ll, ll, ll>> que;
    que.emplace(0, 0, 0, 0);
    vector<vector<vector<ll>>> memo(3,
                                    vector<vector<ll>>(H, vector<ll>(W, -1)));

    // 0: 普通
    // 1: 上下
    // 2: 左右
    while (!que.empty()) {
        ll dis, t, x, y;
        tie(dis, t, x, y) = que.front();
        que.pop();
        if (t == 0 && S[x][y] == '#') continue;
        if (memo[t][x][y] == -1) {
            // cerr <<dis << " "<< t << " " << x << " " << y << endl;
            memo[t][x][y] = dis;
            if (t == 0) {
                if (x != 0) {
                    que.emplace(dis + 1, 0, x - 1, y);
                    que.emplace(dis + 1, 2, x - 1, y);
                }
                if (x != H - 1) {
                    que.emplace(dis + 1, 0, x + 1, y);
                    que.emplace(dis + 1, 2, x, y);
                }
                if (y != 0) {
                    que.emplace(dis + 1, 0, x, y - 1);
                    que.emplace(dis + 1, 1, x, y - 1);
                }
                if (y != W - 1) {
                    que.emplace(dis + 1, 0, x, y + 1);
                    que.emplace(dis + 1, 1, x, y);
                }
            }
            if (t == 1) {
                if (x != 0) { que.emplace(dis + 1, 1, x - 1, y); }
                if (x != H - 1) { que.emplace(dis + 1, 1, x + 1, y); }
                que.emplace(dis + 1, 0, x, y);
                que.emplace(dis + 1, 0, x, y + 1);
            }
            if (t == 2) {
                if (y != 0) { que.emplace(dis + 1, 2, x, y - 1); }
                if (y != W - 1) { que.emplace(dis + 1, 2, x, y + 1); }
                que.emplace(dis + 1, 0, x, y);
                que.emplace(dis + 1, 0, x + 1, y);
            }
        }
    }
    if (memo[0][H - 1][W - 1] == -1) {
        cout << H + W << endl;
        return 0;
    }
    cout << min(H + W,memo[0][H - 1][W - 1]) << endl;
}
0