結果

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

ソースコード

diff #
raw source code 

import sys
from collections import deque

def solve():
    data = sys.stdin.buffer.read().split()
    H, W = map(int, data[:2])
    grid = [row.decode() for row in data[2:]]

    INF = 10**9

    dist = [INF] * (H * W)
    if grid[0][0] != '#':
        dist[0] = 0
        q = deque([0])

        while q:
            v = q.popleft()
            i, j = divmod(v, W)
            nd = dist[v] + 1

            for ni, nj in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
                if 0 <= ni < H and 0 <= nj < W:
                    nv = ni * W + nj
                    if dist[nv] == INF and grid[ni][nj] != '#':
                        dist[nv] = nd
                        q.append(nv)

    best = dist[H*W - 1]

    mS = bytearray(H * W)
    if grid[0][0] != '#':
        mS[0] = 1

    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                continue
            if grid[i][j] == '#':
                continue
            v = i * W + j
            if (i and mS[v - W]) or (j and mS[v - 1]):
                mS[v] = 1

    mG = bytearray(H * W)
    goal = (H - 1) * W + (W - 1)

    if grid[H-1][W-1] != '#':
        mG[goal] = 1

    for i in range(H-1, -1, -1):
        for j in range(W-1, -1, -1):
            if i == H-1 and j == W-1:
                continue
            if grid[i][j] == '#':
                continue

            v = i * W + j
            if (i < H-1 and mG[v + W]) or (j < W-1 and mG[v + 1]):
                mG[v] = 1

    ok = False

    for g in range(H - 1):
        s_min, g_max = W, -1
        a, b = g * W, (g + 1) * W

        for j in range(W):
            if mS[a + j] and j < s_min:
                s_min = j
            if mG[b + j] and j > g_max:
                g_max = j

        if s_min <= g_max:
            ok = True
            break

    if not ok:
        for c in range(W - 1):
            s_min, g_max = H, -1

            for i in range(H):
                if mS[i*W + c] and i < s_min:
                    s_min = i
                if mG[i*W + c + 1] and i > g_max:
                    g_max = i

            if s_min <= g_max:
                ok = True
                break

    if ok:
        best = min(best, H + W - 1)

    best = min(best, H + W)
    print(best)

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