結果

問題 No.3504 Insert Maze
コンテスト
ユーザー lif4635
提出日時 2026-04-18 18:20:22
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 252 ms / 2,000 ms
コード長 1,006 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 228 ms
コンパイル使用メモリ 85,316 KB
実行使用メモリ 117,600 KB
最終ジャッジ日時 2026-04-18 18:20:39
合計ジャッジ時間 13,744 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

"""
H 問題おもしろい

if : 最短経路でない -> 関係ない
ということで最短経路があるかどうかのみかんがえる
"""

from math import isqrt
from collections import deque
import sys

mod = 998244353
input = sys.stdin.readline
II = lambda : int(input())
MI = lambda : (int(_) for _ in input().split())
LI = lambda : list(int(_) for _ in input().split())
SI = lambda : input()

h, w = MI()
c = [SI() for i in range(h)]

ok = [[2] * w for i in range(h)]
ok[0][0] = 0
hs = [w] * h
ws = [h] * w
for i in range(h):
    for j in range(w):
        if c[i][j] == "#": continue
        if i != 0:
            ok[i][j] = min(ok[i][j], ok[i-1][j])
            if hs[i-1] <= j:
                ok[i][j] = min(ok[i][j], 1)
        if j != 0:
            ok[i][j] = min(ok[i][j], ok[i][j-1])
            if ws[j-1] <= i:
                ok[i][j] = min(ok[i][j], 1)
        if ok[i][j] == 0:
            hs[i] = min(hs[i], j)
            ws[j] = min(ws[j], i)

print(h + w - 2 + ok[-1][-1])
0