結果

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

ソースコード

diff #
raw source code 

import sys
from collections import deque
input = sys.stdin.readline
def solve():
    H, W = map(int, input().split())
    grid = [input().strip() for _ in range(H)]
    def passable(r, c):
        return 0 <= r < H and 0 <= c < W and grid[r][c] != '#'
    def orig(r,c): return r*W+c
    def rh(i,j): return H*W + i*W + j
    def ch(i,j): return H*W + (H-1)*W + i*(W-1) + j
    total = H*W + (H-1)*W + H*(W-1)
    dist = [-1]*total
    start = orig(0,0); goal = orig(H-1,W-1)
    dist[start] = 0; q = deque([start])
    while q:
        u = q.popleft(); d = dist[u]
        if u == goal: print(d); return
        if u < H*W:
            r, c = divmod(u, W)
            for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                nr,nc = r+dr, c+dc
                if passable(nr,nc):
                    v = orig(nr,nc)
                    if dist[v]==-1: dist[v]=d+1; q.append(v)
            if passable(r,c):
                for v in ([rh(r-1,c)] if r>0 else []) + ([rh(r,c)] if r<H-1 else []) + ([ch(r,c-1)] if c>0 else []) + ([ch(r,c)] if c<W-1 else []):
                    if dist[v]==-1: dist[v]=d+1; q.append(v)
        elif u < H*W+(H-1)*W:
            i,j = divmod(u-H*W, W)
            for v in ([orig(i,j)] if passable(i,j) else []) + ([orig(i+1,j)] if passable(i+1,j) else []) + ([rh(i,j-1)] if j>0 else []) + ([rh(i,j+1)] if j<W-1 else []):
                if dist[v]==-1: dist[v]=d+1; q.append(v)
        else:
            i,j = divmod(u-H*W-(H-1)*W, W-1)
            for v in ([orig(i,j)] if passable(i,j) else []) + ([orig(i,j+1)] if passable(i,j+1) else []) + ([ch(i-1,j)] if i>0 else []) + ([ch(i+1,j)] if i<H-1 else []):
                if dist[v]==-1: dist[v]=d+1; q.append(v)
    print(-1)
solve()
0