結果

問題 No.3504 Insert Maze
コンテスト
ユーザー 왕지후
提出日時 2026-04-18 01:55:19
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,725 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,415 ms
コンパイル使用メモリ 38,912 KB
実行使用メモリ 99,584 KB
最終ジャッジ日時 2026-04-18 01:55:36
合計ジャッジ時間 16,152 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 85
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

#define INF 65535

static char grid[2005][2005];

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

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

    int R = 2 * H - 1;
    int C = 2 * W - 1;
    int total = R * C;

    // dist: uint16_t is enough because max shortest path <= (2H-2)+(2W-2) <= 7996
    uint16_t *dist = (uint16_t *)malloc(sizeof(uint16_t) * total);
    uint32_t *q = (uint32_t *)malloc(sizeof(uint32_t) * total);

    if (!dist || !q) return 0;

    for (int i = 0; i < total; i++) dist[i] = INF;

    int sr = 0, sc = 0;
    int gr = R - 1, gc = C - 1;

    int sidx = sr * C + sc;
    int gidx = gr * C + gc;

    int head = 0, tail = 0;
    dist[sidx] = 0;
    q[tail++] = sidx;

    const int dr[4] = {-1, 1, 0, 0};
    const int dc[4] = {0, 0, -1, 1};

    while (head < tail) {
        uint32_t v = q[head++];
        if ((int)v == gidx) break;

        int r = v / C;
        int c = v % C;
        uint16_t nd = dist[v] + 1;

        for (int dir = 0; dir < 4; dir++) {
            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;

            // blocked only when both are even and original cell is '#'
            if ((nr % 2 == 0) && (nc % 2 == 0)) {
                if (grid[nr / 2][nc / 2] == '#') continue;
            }

            int ni = nr * C + nc;
            if (dist[ni] != INF) continue;

            dist[ni] = nd;
            q[tail++] = ni;
        }
    }

    if (dist[gidx] == INF) {
        printf("-1\n");
    } else {
        printf("%u\n", dist[gidx]);
    }

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