#1159430 (C) No.3504 Insert Maze

• 問題: No.3504 Insert Maze
• ユーザー: 왕지후
• 提出日時: 2026-04-18 11:22:20
• 言語: C (gcc 15.2.0)
• 結果: AC
• 実行時間: 113 ms / 2,000 ms
• コード長: 3,130 bytes
• コンパイル時間: 2,028 ms
• コンパイル使用メモリ: 40,172 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-18 11:22:30
• 合計ジャッジ時間: 9,745 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

#include <stdio.h>
#include <string.h>

#define INF 1000000000

int H, W;
char grid[2005][2005];

// Using a rolling array of size 3 for the rows to dramatically save memory
int dp[3][4005];

static inline int min_val(int a, int b) {
    return a < b ? a : b;
}

// Checks if a conceptual coordinate is walkable
static inline int valid(int x, int y) {
    if (x < 0 || x >= 2 * H - 1 || y < 0 || y >= 2 * W - 1) {
        return 0;
    }
    // If both coordinates are even, it represents an original grid cell.
    // We cannot enter it if it is a wall '#'.
    if (x % 2 == 0 && y % 2 == 0) {
        if (grid[x / 2][y / 2] == '#') {
            return 0;
        }
    }
    // Odd coordinates represent inserted gaps, which are always safe to traverse.
    return 1;
}

int main() {
    // 1. Read Input
    if (scanf("%d %d", &H, &W) != 2) return 0;
    for (int i = 0; i < H; i++) {
        scanf("%s", grid[i]);
    }

    // 2. Initialize DP table
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 2 * W - 1; j++) {
            dp[i][j] = INF;
        }
    }
    
    // Start at original cell (0, 0)
    dp[0][0] = 0;

    // 3. Process states via DP
    // The DAG strictly moves right (y -> y+1, y+2) and down (x -> x+1, x+2)
    for (int x = 0; x < 2 * H - 1; x++) {
        int cx = x % 3;
        int nx1 = (x + 1) % 3;
        int nx2 = (x + 2) % 3;

        for (int y = 0; y < 2 * W - 1; y++) {
            if (dp[cx][y] >= INF) continue;

            int cur = dp[cx][y];

            // ----- Moving RIGHT -----
            if (y % 2 == 0) {
                // From an original column, we can enter a vertical gap or jump to the next original column
                if (valid(x, y + 1)) dp[cx][y + 1] = min_val(dp[cx][y + 1], cur + 1);
                if (valid(x, y + 2)) dp[cx][y + 2] = min_val(dp[cx][y + 2], cur + 1);
            } else {
                // From a vertical gap, we can enter the adjacent original column
                if (valid(x, y + 1)) dp[cx][y + 1] = min_val(dp[cx][y + 1], cur + 1);
            }

            // ----- Moving DOWN -----
            if (x % 2 == 0) {
                // From an original row, we can enter a horizontal gap or jump to the next original row
                if (valid(x + 1, y)) dp[nx1][y] = min_val(dp[nx1][y], cur + 1);
                if (valid(x + 2, y)) dp[nx2][y] = min_val(dp[nx2][y], cur + 1);
            } else {
                // From a horizontal gap, we can enter the adjacent original row
                if (valid(x + 1, y)) dp[nx1][y] = min_val(dp[nx1][y], cur + 1);
            }
        }

        // We've completed calculating paths reaching the end of the grid logic
        if (x == 2 * H - 2) break;

        // Clear the current active row so it can be reused for row x + 3
        for (int y = 0; y < 2 * W - 1; y++) {
            dp[cx][y] = INF;
        }
    }

    // 4. Extract Answer
    // The goal is the original cell at the bottom-right corner
    int ans = dp[(2 * H - 2) % 3][2 * W - 2];
    
    if (ans >= INF) {
        printf("-1\n");
    } else {
        printf("%d\n", ans);
    }

    return 0;
}