結果

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

ソースコード

diff #
raw source code 

import sys

input = sys.stdin.readline

h, w = map(int, input().split())
g = [input().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 = [INF] * (w - 1)
    c = [INF] * w
    d = [INF] * (w - 1)

    for col in range(w):
        now = INF

        if r == 0 and col == 0:
            now = 0

        if row[col] != '#':
            if r:
                x = up_a[col]
                if x < now:
                    now = x
                x = up_c[col]
                if x < now:
                    now = x

            if col:
                x = a[col - 1]
                if x < now:
                    now = x
                x = b[col - 1]
                if x < now:
                    now = x

        a[col] = now

        if col + 1 < w:
            x = now + 1
            if r:
                y = up_b[col]
                if y < x:
                    x = y
                y = up_d[col]
                if y < x:
                    x = y
            b[col] = x

        if r + 1 < h:
            x = now + 1
            if col:
                y = c[col - 1]
                if y < x:
                    x = y
                y = d[col - 1]
                if y < x:
                    x = y
            c[col] = x

        if r + 1 < h and col + 1 < w:
            x = b[col]
            if c[col] < x:
                x = c[col]
            d[col] = x + 1

    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