結果

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

ソースコード

diff #
raw source code 

import sys
from collections import deque

def solve():
    input = sys.stdin.read().split()
    if not input:
        return
    
    H = int(input[0])
    W = int(input[1])
    grid = input[2:]
    inf = float('inf')
    dist = [[[inf] * 3 for _ in range(W)] for _ in range(H)]
    
    dq = deque([(0, 0, 0)])
    dist[0][0][0] = 0
    
    while dq:
        r, c, t = dq.popleft()
        d = dist[r][c][t]
        
        if t == 0:
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] != '#':
                    if dist[nr][nc][0] > d + 1:
                        dist[nr][nc][0] = d + 1
                        dq.append((nr, nc, 0))
            
            if r + 1 < H:
                if dist[r][c][1] > d + 1:
                    dist[r][c][1] = d + 1
                    dq.append((r, c, 1))
            if r - 1 >= 0:
                if dist[r-1][c][1] > d + 1:
                    dist[r-1][c][1] = d + 1
                    dq.append((r-1, c, 1))
            
            if c + 1 < W:
                if dist[r][c][2] > d + 1:
                    dist[r][c][2] = d + 1
                    dq.append((r, c, 2))
            if c - 1 >= 0:
                if dist[r][c-1][2] > d + 1:
                    dist[r][c-1][2] = d + 1
                    dq.append((r, c-1, 2))
                    
        elif t == 1:
            for dc in [1, -1]:
                nc = c + dc
                if 0 <= nc < W:
                    if dist[r][nc][1] > d + 1:
                        dist[r][nc][1] = d + 1
                        dq.append((r, nc, 1))
            for nr in [r, r + 1]:
                if dist[nr][c][0] > d + 1:
                    dist[nr][c][0] = d + 1
                    dq.append((nr, c, 0))
                    
        elif t == 2:
            for dr in [1, -1]:
                nr = r + dr
                if 0 <= nr < H:
                    if dist[nr][c][2] > d + 1:
                        dist[nr][c][2] = d + 1
                        dq.append((nr, c, 2))
            for nc in [c, c + 1]:
                if dist[r][nc][0] > d + 1:
                    dist[r][nc][0] = d + 1
                    dq.append((r, nc, 0))

    ans = dist[H-1][W-1][0]
    print(ans if ans != inf else -1)

solve()
0