結果

問題 No.3504 Insert Maze
コンテスト
ユーザー e032_Ashmit_Rana
提出日時 2026-04-19 20:09:41
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 1,290 ms / 2,000 ms
コード長 2,234 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 486 ms
コンパイル使用メモリ 20,700 KB
実行使用メモリ 25,176 KB
最終ジャッジ日時 2026-04-19 20:10:42
合計ジャッジ時間 56,280 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys


def main() -> None:
    input = sys.stdin.readline
    h, w = map(int, input().split())
    grid = [input().strip() for _ in range(h)]

    start = [bytearray(w) for _ in range(h)]
    goal = [bytearray(w) for _ in range(h)]

    for i in range(h):
        gi = grid[i]
        si = start[i]
        prev = start[i - 1] if i else None
        for j, ch in enumerate(gi):
            if ch == "#":
                continue
            if i == 0 and j == 0:
                si[j] = 1
            elif (j and si[j - 1]) or (i and prev[j]):
                si[j] = 1

    base = h + w - 2
    if start[h - 1][w - 1]:
        print(base)
        return

    for i in range(h - 1, -1, -1):
        gi = grid[i]
        goali = goal[i]
        nxt = goal[i + 1] if i + 1 < h else None
        for j in range(w - 1, -1, -1):
            if gi[j] == "#":
                continue
            if i == h - 1 and j == w - 1:
                goali[j] = 1
            elif (j + 1 < w and goali[j + 1]) or (i + 1 < h and nxt[j]):
                goali[j] = 1

    # Insert one horizontal all-open row between rows r and r+1.
    for r in range(h - 1):
        left_entry = None
        sr = start[r]
        for j in range(w):
            if sr[j]:
                left_entry = j
                break
        if left_entry is None:
            continue

        right_exit = None
        gr = goal[r + 1]
        for j in range(w - 1, -1, -1):
            if gr[j]:
                right_exit = j
                break
        if right_exit is not None and left_entry <= right_exit:
            print(base + 1)
            return

    # Insert one vertical all-open column between columns c and c+1.
    for c in range(w - 1):
        top_entry = None
        for i in range(h):
            if start[i][c]:
                top_entry = i
                break
        if top_entry is None:
            continue

        bottom_exit = None
        for i in range(h - 1, -1, -1):
            if goal[i][c + 1]:
                bottom_exit = i
                break
        if bottom_exit is not None and top_entry <= bottom_exit:
            print(base + 1)
            return

    print(base + 2)


if __name__ == "__main__":
    main()
0