結果

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

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

const int INF = 1e9;

struct State {
    int r, c, type;
};

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

    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)));
    queue<State> q;

    dist[0][0][0] = 0;
    q.push({0, 0, 0});

    while (!q.empty()) {
        State curr = q.front();
        q.pop();
        int d = dist[curr.r][curr.c][curr.type];

        if (curr.type == 0) {
            int dr[] = {0, 0, 1, -1};
            int dc[] = {1, -1, 0, 0};
            for (int i = 0; i < 4; i++) {
                int nr = curr.r + dr[i], nc = curr.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;
                        q.push({nr, nc, 0});
                    }
                }
            }
            if (curr.r + 1 < H) {
                if (dist[curr.r][curr.c][1] > d + 1) {
                    dist[curr.r][curr.c][1] = d + 1;
                    q.push({curr.r, curr.c, 1});
                }
            }
            if (curr.r - 1 >= 0) {
                if (dist[curr.r - 1][curr.c][1] > d + 1) {
                    dist[curr.r - 1][curr.c][1] = d + 1;
                    q.push({curr.r - 1, curr.c, 1});
                }
            }
            if (curr.c + 1 < W) {
                if (dist[curr.r][curr.c][2] > d + 1) {
                    dist[curr.r][curr.c][2] = d + 1;
                    q.push({curr.r, curr.c, 2});
                }
            }
            if (curr.c - 1 >= 0) {
                if (dist[curr.r][curr.c - 1][2] > d + 1) {
                    dist[curr.r][curr.c - 1][2] = d + 1;
                    q.push({curr.r, curr.c - 1, 2});
                }
            }
        } else if (curr.type == 1) {
            int dr[] = {0, 0};
            int dc[] = {1, -1};
            for (int i = 0; i < 2; i++) {
                int nr = curr.r, nc = curr.c + dc[i];
                if (nc >= 0 && nc < W) {
                    if (dist[nr][nc][1] > d + 1) {
                        dist[nr][nc][1] = d + 1;
                        q.push({nr, nc, 1});
                    }
                }
            }
            for (int nr : {curr.r, curr.r + 1}) {
                if (dist[nr][curr.c][0] > d + 1) {
                    dist[nr][curr.c][0] = d + 1;
                    q.push({nr, curr.c, 0});
                }
            }
        } else if (curr.type == 2) {
            int dr[] = {1, -1};
            int dc[] = {0, 0};
            for (int i = 0; i < 2; i++) {
                int nr = curr.r + dr[i], nc = curr.c;
                if (nr >= 0 && nr < H) {
                    if (dist[nr][nc][2] > d + 1) {
                        dist[nr][nc][2] = d + 1;
                        q.push({nr, nc, 2});
                    }
                }
            }
            for (int nc : {curr.c, curr.c + 1}) {
                if (dist[curr.r][nc][0] > d + 1) {
                    dist[curr.r][nc][0] = d + 1;
                    q.push({curr.r, nc, 0});
                }
            }
        }
    }

    int result = dist[H - 1][W - 1][0];
    if (result == INF) cout << -1 << endl;
    else cout << result << endl;

    return 0;
}
0