結果

問題 No.3504 Insert Maze
コンテスト
ユーザー ,
提出日時 2026-04-19 16:22:45
言語 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
結果
AC  
実行時間 191 ms / 2,000 ms
コード長 3,376 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 455 ms
コンパイル使用メモリ 45,312 KB
実行使用メモリ 46,848 KB
最終ジャッジ日時 2026-04-19 16:22:59
合計ジャッジ時間 13,479 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

#define MAXN 2002
#define MAXHW (MAXN * MAXN)

int H, W;
char grid[MAXN][MAXN];
int dist_arr[MAXHW];
int queue_arr[MAXHW];

char mS[MAXHW];
char mG[MAXHW];

static inline int idx(int i, int j) {
    return i * W + j;
}

void bfs0() {
    int HW = H * W;

    for (int i = 0; i < HW; i++)
        dist_arr[i] = -1;

    if (grid[0][0] == '#')
        return;

    dist_arr[0] = 0;

    int head = 0, tail = 0;
    queue_arr[tail++] = 0;

    while (head < tail) {
        int pos = queue_arr[head++];
        int i = pos / W;
        int j = pos % W;
        int d = dist_arr[pos] + 1;

        if (i > 0) {
            int np = pos - W;
            if (dist_arr[np] == -1 && grid[i - 1][j] != '#') {
                dist_arr[np] = d;
                queue_arr[tail++] = np;
            }
        }

        if (i < H - 1) {
            int np = pos + W;
            if (dist_arr[np] == -1 && grid[i + 1][j] != '#') {
                dist_arr[np] = d;
                queue_arr[tail++] = np;
            }
        }

        if (j > 0) {
            int np = pos - 1;
            if (dist_arr[np] == -1 && grid[i][j - 1] != '#') {
                dist_arr[np] = d;
                queue_arr[tail++] = np;
            }
        }

        if (j < W - 1) {
            int np = pos + 1;
            if (dist_arr[np] == -1 && grid[i][j + 1] != '#') {
                dist_arr[np] = d;
                queue_arr[tail++] = np;
            }
        }
    }
}

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

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

    bfs0();

    int d0 = dist_arr[idx(H - 1, W - 1)];
    int best = (d0 < 0) ? H + W + 1 : d0;

    memset(mS, 0, H * W);
    if (grid[0][0] != '#') mS[0] = 1;

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (i == 0 && j == 0) continue;
            if (grid[i][j] == '#') continue;

            if ((i > 0 && mS[idx(i - 1, j)]) ||
                (j > 0 && mS[idx(i, j - 1)]))
                mS[idx(i, j)] = 1;
        }
    }

    memset(mG, 0, H * W);
    if (grid[H - 1][W - 1] != '#')
        mG[idx(H - 1, W - 1)] = 1;

    for (int i = H - 1; i >= 0; i--) {
        for (int j = W - 1; j >= 0; j--) {
            if (i == H - 1 && j == W - 1) continue;
            if (grid[i][j] == '#') continue;

            if ((i < H - 1 && mG[idx(i + 1, j)]) ||
                (j < W - 1 && mG[idx(i, j + 1)]))
                mG[idx(i, j)] = 1;
        }
    }

    int one_ins = 0;

    for (int g = 0; g < H - 1 && !one_ins; g++) {
        int min_s = W, max_g = -1;

        for (int j = 0; j < W; j++) {
            if (mS[idx(g, j)] && j < min_s)
                min_s = j;
            if (mG[idx(g + 1, j)] && j > max_g)
                max_g = j;
        }

        if (min_s <= max_g)
            one_ins = 1;
    }

    for (int c = 0; c < W - 1 && !one_ins; c++) {
        int min_s = H, max_g = -1;

        for (int i = 0; i < H; i++) {
            if (mS[idx(i, c)] && i < min_s)
                min_s = i;
            if (mG[idx(i, c + 1)] && i > max_g)
                max_g = i;
        }

        if (min_s <= max_g)
            one_ins = 1;
    }

    if (one_ins && H + W - 1 < best)
        best = H + W - 1;

    if (H + W < best)
        best = H + W;

    printf("%d\n", best);

    return 0;
}
0