結果

問題 No.3504 Insert Maze
コンテスト
ユーザー titia
提出日時 2026-04-17 21:26:37
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,125 ms / 2,000 ms
コード長 1,388 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 817 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 216,704 KB
最終ジャッジ日時 2026-04-17 21:26:56
合計ジャッジ時間 16,122 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline
from collections import deque

H,W=list(map(int,input().split()))

MAP=[input().strip() for i in range(H)]

ANS=H+W

D=[[1<<30]*W for i in range(H)]
D[0][0]=0
Q=deque()
Q.append((0,0))

while Q:
    x,y=Q.popleft()

    for z,w in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
        if 0<=z<H and 0<=w<W:
            if MAP[z][w]=="#":
                continue
            if D[z][w]>D[x][y]+1:
                Q.append((z,w))
                D[z][w]=D[x][y]+1

ANS=min(ANS,D[H-1][W-1])

X=[[0]*W for i in range(H)]
X[0][0]=1
Q=[(0,0)]
while Q:
    x,y=Q.pop()

    for z,w in [(x+1,y),(x,y+1)]:
        if 0<=z<H and 0<=w<W:
            if MAP[z][w]=="#":
                continue
            if X[z][w]==0:
                X[z][w]=1
                Q.append((z,w))

Y=[[0]*W for i in range(H)]
Y[H-1][W-1]=1
Q=[(H-1,W-1)]
while Q:
    x,y=Q.pop()

    for z,w in [(x-1,y),(x,y-1)]:
        if 0<=z<H and 0<=w<W:
            if MAP[z][w]=="#":
                continue
            if Y[z][w]==0:
                Y[z][w]=1
                Q.append((z,w))

XX=0
XY=0

YX=H-1
YY=W-1

for i in range(H):
    for j in range(W):
        if X[i][j]==1:
            XX=max(XX,i)
            XY=max(XY,j)

        if Y[i][j]==1:
            YX=min(YX,i)
            YY=min(YY,j)


if XX>=YX-1:
    ANS=min(ANS,H+W-1)

if XY>=YY-1:
    ANS=min(ANS,H+W-1)

print(ANS)
0