#1159918 (C) No.3504 Insert Maze

• 問題: No.3504 Insert Maze
• ユーザー: gojoxd
• 提出日時: 2026-04-18 18:35:21
• 言語: C (gcc 15.2.0)
• 結果: AC
• 実行時間: 456 ms / 2,000 ms
• コード長: 4,470 bytes
• コンパイル時間: 798 ms
• コンパイル使用メモリ: 40,644 KB
• 実行使用メモリ: 193,280 KB
• 最終ジャッジ日時: 2026-04-18 18:35:56
• 合計ジャッジ時間: 23,251 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

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

ソースコード

/*
 * No.3504 Insert Maze
 * https://yukicoder.me/problems/13152
 *
 * PROBLEM:
 * Given an H×W grid with S at (1,1), G at (H,W), walls '#', and paths '.'.
 * Before moving, you may insert any number of all-'.' rows between adjacent
 * rows, and/or all-'.' columns between adjacent columns (each insertion is free).
 * Find the minimum number of moves to reach G from S in the modified grid, or -1.
 *
 * KEY INSIGHT — EXPANDED GRID MODEL:
 * Build a (2H-1) × (2W-1) virtual grid:
 *   - Even (r,c): original cell grid[r/2][c/2]
 *   - Odd r or c: a "gap" cell representing an inserted row/column — always '.'
 *
 * Movement in real game:
 *  1. Standard move to adjacent cell in expanded grid (cost 1).
 *     Gap cells are always passable; original cells must be non-wall.
 *  2. "Skip" move: jump over a gap intermediate to reach an expanded-distance-2
 *     neighbor at cost 1. This models NOT inserting a row/col between two
 *     original rows/cols (they remain directly adjacent at cost 1).
 *     The intermediate must be a gap cell (always passable) for the skip to apply.
 *
 * Both move types cost 1, so BFS with a stale-entry check suffices.
 *
 * COMPLEXITY: O(H * W) time and space.
 * MEMORY: ~61 MB for dist array + ~122 MB for queue = ~183 MB total.
 */

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

#define MAXH  2001
#define MAXW  2001
#define MAXER (2*MAXH - 1)   /* 4001 */
#define MAXEC (2*MAXW - 1)   /* 4001 */
#define INF   0x3f3f3f3f

static int   H, W, ER, EC;
static char  grid[MAXH][MAXW];
static int   dist[MAXER][MAXEC];

/* BFS circular queue */
typedef struct { int r, c; } Point;
static Point *Q;
static int    qhead, qtail, qcap;

static inline void enq(int r, int c) {
    Q[qtail].r = r;
    Q[qtail].c = c;
    if (++qtail == qcap) qtail = 0;
}

static inline Point deq(void) {
    Point p = Q[qhead];
    if (++qhead == qcap) qhead = 0;
    return p;
}

/* Is the expanded-grid cell (er,ec) passable? */
static inline int passable(int er, int ec) {
    /* Bounds check using unsigned comparison */
    if ((unsigned)er >= (unsigned)ER || (unsigned)ec >= (unsigned)EC)
        return 0;
    /* Gap cells (odd row or col index) are always '.' */
    if ((er & 1) || (ec & 1))
        return 1;
    /* Original cell: passable unless wall */
    return grid[er >> 1][ec >> 1] != '#';
}

static inline void relax(int nr, int nc, int d) {
    if (passable(nr, nc) && dist[nr][nc] > d) {
        dist[nr][nc] = d;
        enq(nr, nc);
    }
}

int main(void) {
    scanf("%d %d", &H, &W);
    for (int i = 0; i < H; i++)
        scanf("%s", grid[i]);

    ER = 2 * H - 1;
    EC = 2 * W - 1;

    memset(dist, 0x3f, sizeof(dist));

    /* Queue capacity: 2× total nodes to handle multiple enqueues */
    qcap  = ER * EC * 2 + 10;
    Q     = (Point *)malloc((size_t)qcap * sizeof(Point));
    if (!Q) { fprintf(stderr, "malloc failed\n"); return 1; }
    qhead = qtail = 0;

    if (!passable(0, 0)) {
        printf("-1\n");
        free(Q);
        return 0;
    }

    dist[0][0] = 0;
    enq(0, 0);

    while (qhead != qtail) {
        Point p = deq();
        int r = p.r, c = p.c, d = dist[r][c];

        /* --- Standard 4-directional moves (cost 1) --- */
        relax(r - 1, c, d + 1);
        relax(r + 1, c, d + 1);
        relax(r, c - 1, d + 1);
        relax(r, c + 1, d + 1);

        /*
         * --- Skip moves (cost 1): jump over a gap intermediate ---
         * A "skip" from (r,c) to (r±2,c) is valid when the intermediate
         * cell (r±1, c) is a gap (odd row index), i.e., always passable.
         * This models direct adjacency between original cells with no
         * inserted row between them.
         * Similarly for horizontal skips via gap columns (odd col index).
         */

        /* Skip down: intermediate (r+1, c) must be a gap row */
        if ((r + 1 < ER) && ((r + 1) & 1))
            relax(r + 2, c, d + 1);

        /* Skip up: intermediate (r-1, c) must be a gap row */
        if ((r - 1 >= 0) && ((r - 1) & 1))
            relax(r - 2, c, d + 1);

        /* Skip right: intermediate (r, c+1) must be a gap col */
        if ((c + 1 < EC) && ((c + 1) & 1))
            relax(r, c + 2, d + 1);

        /* Skip left: intermediate (r, c-1) must be a gap col */
        if ((c - 1 >= 0) && ((c - 1) & 1))
            relax(r, c - 2, d + 1);
    }

    int ans = dist[ER - 1][EC - 1];
    printf("%d\n", ans == INF ? -1 : ans);

    free(Q);
    return 0;
}