#1159908 (C) No.3504 Insert Maze

• 問題: No.3504 Insert Maze
• ユーザー: gojoxd
• 提出日時: 2026-04-18 18:25:04
• 言語: C (gcc 15.2.0)
• 結果: WA
• 実行時間: -
• コード長: 7,104 bytes
• コンパイル時間: 406 ms
• コンパイル使用メモリ: 42,928 KB
• 実行使用メモリ: 130,816 KB
• 最終ジャッジ日時: 2026-04-18 18:25:26
• 合計ジャッジ時間: 17,962 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

/*
 * No.3504 Insert Maze
 *
 * Key idea: We can insert any number of all-'.' rows/columns.
 * Model this as a Dijkstra on an extended graph with 4 node types:
 *   Type 0: Grid cell (i,j)          — H*W nodes
 *   Type 1: Row-corridor (r,j)       — (H-1)*W nodes  [between row r and r+1, at column j]
 *   Type 2: Col-corridor (i,c)       — H*(W-1) nodes  [between col c and c+1, at row i]
 *   Type 3: Intersection (r,c)       — (H-1)*(W-1) nodes [row-corridor r meets col-corridor c]
 *
 * Edges (cost 1 each):
 *   Grid(i,j) <-> Grid neighbor (if passable)
 *   Grid(i,j) <-> RowCorridor(i-1,j)   [enter corridor above]
 *   Grid(i,j) <-> RowCorridor(i,j)     [enter corridor below]
 *   Grid(i,j) <-> ColCorridor(i,j-1)   [enter corridor left]
 *   Grid(i,j) <-> ColCorridor(i,j)     [enter corridor right]
 *   RowCorridor(r,j) <-> RowCorridor(r,j±1)
 *   RowCorridor(r,j) <-> Intersection(r,j-1)  [enter col-corridor left]
 *   RowCorridor(r,j) <-> Intersection(r,j)    [enter col-corridor right]
 *   ColCorridor(i,c) <-> ColCorridor(i±1,c)
 *   ColCorridor(i,c) <-> Intersection(i-1,c)  [enter row-corridor above]
 *   ColCorridor(i,c) <-> Intersection(i,c)    [enter row-corridor below]
 *   Intersection(r,c) <-> Intersection(r,c±1) [move along row-corridor]
 *   Intersection(r,c) <-> Intersection(r±1,c) [move along col-corridor]
 *
 * Total nodes ~ 4*H*W <= 16*10^6 with H,W<=2000.
 * Using Dijkstra with binary heap (all edge weights = 1, so BFS works too).
 */

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

#define MAXH 2001
#define MAXW 2001

static int H, W;
static char grid[MAXH][MAXW];

/* Node encoding */
/* We use int node IDs */
/* Type 0: Grid(i,j)         id = i*W + j                        range [0, H*W) */
/* Type 1: RowCor(r,j)       id = H*W + r*W + j                  range [H*W, H*W+(H-1)*W) */
/* Type 2: ColCor(i,c)       id = H*W+(H-1)*W + i*(W-1) + c      range [..., ...+H*(W-1)) */
/* Type 3: Inter(r,c)        id = above + H*(W-1) + r*(W-1) + c  range [...] */

static int base1, base2, base3, total_nodes;

static inline int grid_id(int i, int j) { return i*W + j; }
static inline int rowcor_id(int r, int j) { return base1 + r*W + j; }
static inline int colcor_id(int i, int c) { return base2 + i*(W-1) + c; }
static inline int inter_id(int r, int c)  { return base3 + r*(W-1) + c; }

/* BFS queue (all edges weight 1) */
static int *dist;
static int *queue;

static inline int passable(int i, int j) {
    return grid[i][j] != '#';
}

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

    base1 = H * W;
    base2 = base1 + (H-1) * W;
    base3 = base2 + H * (W-1);
    total_nodes = base3 + (H-1) * (W-1);

    dist = (int*)malloc(total_nodes * sizeof(int));
    queue = (int*)malloc(total_nodes * 2 * sizeof(int)); /* BFS queue, worst case each node once */
    
    /* Use a simple BFS since all edges cost 1 */
    /* But queue might need re-visits... actually BFS is fine since all costs are 1 */
    for (int i = 0; i < total_nodes; i++) dist[i] = -1;

    int start = grid_id(0, 0);
    int goal  = grid_id(H-1, W-1);
    dist[start] = 0;

    /* BFS with a queue */
    /* Queue size: in worst case O(total_nodes) */
    int qhead = 0, qtail = 0;
    /* We need queue of size total_nodes */
    /* Realloc to be safe */
    free(queue);
    queue = (int*)malloc(total_nodes * sizeof(int));

    queue[qtail++] = start;

#define PUSH(nd, d) do { \
    if ((nd) >= 0 && (nd) < total_nodes && dist[nd] == -1) { \
        dist[nd] = (d); \
        queue[qtail++] = (nd); \
    } \
} while(0)

    int di[] = {-1, 1, 0, 0};
    int dj[] = {0, 0, -1, 1};

    while (qhead < qtail) {
        int u = queue[qhead++];
        int d = dist[u];

        if (u < base1) {
            /* Grid node (i,j) */
            int i = u / W, j = u % W;
            /* 4-directional moves within grid */
            for (int dir = 0; dir < 4; dir++) {
                int ni = i + di[dir], nj = j + dj[dir];
                if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
                if (!passable(ni, nj)) continue;
                PUSH(grid_id(ni, nj), d+1);
            }
            /* Enter row corridor above (between row i-1 and i) */
            if (i > 0) PUSH(rowcor_id(i-1, j), d+1);
            /* Enter row corridor below (between row i and i+1) */
            if (i < H-1) PUSH(rowcor_id(i, j), d+1);
            /* Enter col corridor left (between col j-1 and j) */
            if (j > 0) PUSH(colcor_id(i, j-1), d+1);
            /* Enter col corridor right (between col j and j+1) */
            if (j < W-1) PUSH(colcor_id(i, j), d+1);
        } else if (u < base2) {
            /* RowCorridor(r, j): between row r and r+1, at column j */
            int tmp = u - base1;
            int r = tmp / W, j = tmp % W;
            /* Move horizontally along row corridor */
            if (j > 0)   PUSH(rowcor_id(r, j-1), d+1);
            if (j < W-1) PUSH(rowcor_id(r, j+1), d+1);
            /* Exit to grid above (row r) or below (row r+1) */
            PUSH(grid_id(r, j),   d+1);
            PUSH(grid_id(r+1, j), d+1);
            /* Enter col corridor to the left (between col j-1 and j) — intersection */
            if (j > 0)   PUSH(inter_id(r, j-1), d+1);
            /* Enter col corridor to the right (between col j and j+1) — intersection */
            if (j < W-1) PUSH(inter_id(r, j), d+1);
        } else if (u < base3) {
            /* ColCorridor(i, c): between col c and c+1, at row i */
            int tmp = u - base2;
            int i = tmp / (W-1), c = tmp % (W-1);
            /* Move vertically along col corridor */
            if (i > 0)   PUSH(colcor_id(i-1, c), d+1);
            if (i < H-1) PUSH(colcor_id(i+1, c), d+1);
            /* Exit to grid left (col c) or right (col c+1) */
            PUSH(grid_id(i, c),   d+1);
            PUSH(grid_id(i, c+1), d+1);
            /* Enter row corridor above (between row i-1 and i) — intersection */
            if (i > 0)   PUSH(inter_id(i-1, c), d+1);
            /* Enter row corridor below (between row i and i+1) — intersection */
            if (i < H-1) PUSH(inter_id(i, c), d+1);
        } else {
            /* Intersection(r, c): row-gap r meets col-gap c */
            int tmp = u - base3;
            int r = tmp / (W-1), c = tmp % (W-1);
            /* Move along row corridor (horizontally) */
            if (c > 0)   PUSH(inter_id(r, c-1), d+1);
            if (c < W-2) PUSH(inter_id(r, c+1), d+1);
            /* Move along col corridor (vertically) */
            if (r > 0)   PUSH(inter_id(r-1, c), d+1);
            if (r < H-2) PUSH(inter_id(r+1, c), d+1);
            /* Exit to RowCorridor(r, c) or RowCorridor(r, c+1) */
            PUSH(rowcor_id(r, c),   d+1);
            PUSH(rowcor_id(r, c+1), d+1);
            /* Exit to ColCorridor(r, c) or ColCorridor(r+1, c) */
            PUSH(colcor_id(r, c),   d+1);
            PUSH(colcor_id(r+1, c), d+1);
        }
    }

    printf("%d\n", dist[goal]);

    free(dist);
    free(queue);
    return 0;
}