結果

問題 No.3504 Insert Maze
コンテスト
ユーザー 왕지후
提出日時 2026-04-18 02:14:06
言語 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,249 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 401 ms
コンパイル使用メモリ 43,624 KB
実行使用メモリ 70,528 KB
最終ジャッジ日時 2026-04-18 02:14:24
合計ジャッジ時間 12,830 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44 WA * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>
#include <stdlib.h>

#define INF 1000000000

static char C[2005][2005];
static int dp[4005][4005];

static inline int open_cell(int r, int c, int H, int W) {
    if (r < 0 || r >= 2 * H - 1 || c < 0 || c >= 2 * W - 1) return 0;
    if ((r % 2 == 0) && (c % 2 == 0)) {
        return C[r / 2][c / 2] != '#';
    }
    return 1;
}

static inline void chmin(int *a, int b) {
    if (b < *a) *a = b;
}

int main(void) {
    int H, W;
    scanf("%d %d", &H, &W);

    for (int i = 0; i < H; i++) {
        scanf("%s", C[i]);
    }

    int R = 2 * H - 1;
    int S = 2 * W - 1;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < S; j++) {
            dp[i][j] = INF;
        }
    }

    dp[0][0] = 0;

    for (int r = 0; r < R; r++) {
        for (int c = 0; c < S; c++) {
            if (!open_cell(r, c, H, W)) continue;
            if (dp[r][c] == INF) continue;

            // 1칸 오른쪽: odd col로 들어가는 경우만 +1
            if (c + 1 < S && open_cell(r, c + 1, H, W)) {
                int cost = (c % 2 == 0 ? 1 : 0);
                chmin(&dp[r][c + 1], dp[r][c] + cost);
            }

            // 1칸 아래: odd row로 들어가는 경우만 +1
            if (r + 1 < R && open_cell(r + 1, c, H, W)) {
                int cost = (r % 2 == 0 ? 1 : 0);
                chmin(&dp[r + 1][c], dp[r][c] + cost);
            }

            // 2칸 오른쪽: 삽입 없이 원래 간격을 그대로 건넘
            if (c + 2 < S && open_cell(r, c + 2, H, W)) {
                // odd -> odd 로 건너뛸 때는 중간 even 칸이 실제로 지나갈 수 있어야 함
                if (!(c % 2 == 1 && !open_cell(r, c + 1, H, W))) {
                    chmin(&dp[r][c + 2], dp[r][c]);
                }
            }

            // 2칸 아래: 삽입 없이 원래 간격을 그대로 건넘
            if (r + 2 < R && open_cell(r + 2, c, H, W)) {
                if (!(r % 2 == 1 && !open_cell(r + 1, c, H, W))) {
                    chmin(&dp[r + 2][c], dp[r][c]);
                }
            }
        }
    }

    int extra = dp[R - 1][S - 1];
    if (extra == INF) {
        printf("-1\n");
    } else {
        printf("%d\n", (H - 1) + (W - 1) + extra);
    }

    return 0;
}
0