結果

問題 No.3504 Insert Maze
コンテスト
ユーザー rumblycascade7
提出日時 2026-04-18 05:37:14
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 1,832 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 602 ms
コンパイル使用メモリ 20,700 KB
実行使用メモリ 15,360 KB
最終ジャッジ日時 2026-04-18 05:38:18
合計ジャッジ時間 16,165 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 TLE * 1 -- * 57
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

rd = sys.stdin.buffer.readline

h, w = map(int, rd().split())
g = [rd().strip() for _ in range(h)]

INF = 10 ** 18

up_a = [INF] * w
up_b = [INF] * (w - 1)
up_c = [INF] * w
up_d = [INF] * (w - 1)

for r in range(h):
    row = g[r]

    a = [INF] * w
    b = [0] * (w - 1)
    c = [0] * w
    d = [0] * (w - 1)

    ua = up_a
    ub = up_b
    uc = up_c
    ud = up_d

    left_a = INF
    left_b = INF
    left_c = INF
    left_d = INF

    down_ok = r + 1 < h
    top = r > 0
    start_row = r == 0

    for j in range(w):
        cur = 0 if (start_row and j == 0) else INF

        if row[j] != 35:
            x = ua[j]
            if x < cur:
                cur = x

            x = uc[j]
            if x < cur:
                cur = x

            if left_a < cur:
                cur = left_a

            if left_b < cur:
                cur = left_b

        a[j] = cur

        if j + 1 < w:
            x = cur + 1
            if top:
                y = ub[j]
                if y < x:
                    x = y
                y = ud[j]
                if y < x:
                    x = y
            b[j] = x
        else:
            x = 0

        if down_ok:
            y = cur + 1
            if j:
                if left_c < y:
                    y = left_c
                if left_d < y:
                    y = left_d
            c[j] = y
        else:
            y = 0

        if down_ok and j + 1 < w:
            z = x
            if y < z:
                z = y
            d[j] = z + 1

        left_a = cur
        if j + 1 < w:
            left_b = b[j]
        if down_ok:
            left_c = c[j]
            if j + 1 < w:
                left_d = d[j]

    up_a = a
    up_b = b
    up_c = c
    up_d = d

res = up_a[-1]
if res >= INF:
    print(-1)
else:
    print(res + h + w - 2)
0