結果

問題 No.3504 Insert Maze
コンテスト
ユーザー kuma-1971
提出日時 2026-04-18 04:37:29
言語 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
結果
WA  
実行時間 -
コード長 2,696 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,081 ms
コンパイル使用メモリ 179,144 KB
実行使用メモリ 230,016 KB
最終ジャッジ日時 2026-04-18 04:38:16
合計ジャッジ時間 38,492 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 82 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <string>
#include <deque>

using namespace std;

const int INF = 1e9;

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

    vector<vector<vector<int>>> dist(H, vector<vector<int>>(W, vector<int>(3, INF)));
    deque<pair<pair<int, int>, int>> dq;

    dist[0][0][0] = 0;
    dq.push_front({{0, 0}, 0});

    int dr[] = {0, 0, 1, -1};
    int dc[] = {1, -1, 0, 0};

    while (!dq.empty()) {
        int r = dq.front().first.first;
        int c = dq.front().first.second;
        int s = dq.front().second;
        int d = dist[r][c][s];
        dq.pop_front();

        if (s == 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 && C[nr][nc] != '#') {
                    if (dist[nr][nc][0] > d + 1) {
                        dist[nr][nc][0] = d + 1;
                        dq.push_back({{nr, nc}, 0});
                    }
                }
            }
            if (dist[r][c][1] > d + 1) {
                dist[r][c][1] = d + 1;
                dq.push_back({{r, c}, 1});
            }
            if (dist[r][c][2] > d + 1) {
                dist[r][c][2] = d + 1;
                dq.push_back({{r, c}, 2});
            }
        } 
        else if (s == 1) {
            for (int nc : {c - 1, c + 1}) {
                if (nc >= 0 && nc < W) {
                    if (dist[r][nc][1] > d + 1) {
                        dist[r][nc][1] = d + 1;
                        dq.push_back({{r, nc}, 1});
                    }
                }
            }
            for (int nr : {r, r + 1}) {
                if (nr >= 0 && nr < H) {
                    if (dist[nr][c][0] > d + 1) {
                        dist[nr][c][0] = d + 1;
                        dq.push_back({{nr, c}, 0});
                    }
                }
            }
        } 
        else if (s == 2) {
            for (int nr : {r - 1, r + 1}) {
                if (nr >= 0 && nr < H) {
                    if (dist[nr][c][2] > d + 1) {
                        dist[nr][c][2] = d + 1;
                        dq.push_back({{nr, c}, 2});
                    }
                }
            }
            for (int nc : {c, c + 1}) {
                if (nc >= 0 && nc < W) {
                    if (dist[r][nc][0] > d + 1) {
                        dist[r][nc][0] = d + 1;
                        dq.push_back({{r, nc}, 0});
                    }
                }
            }
        }
    }

    int ans = dist[H - 1][W - 1][0];
    cout << (ans == INF ? -1 : ans) << endl;

    return 0;
}
0