結果

問題 No.3504 Insert Maze
コンテスト
ユーザー Qiu Tian
提出日時 2026-04-18 17:49:06
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WA  
実行時間 -
コード長 1,379 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 622 ms
コンパイル使用メモリ 20,696 KB
実行使用メモリ 98,676 KB
最終ジャッジ日時 2026-04-18 17:50:26
合計ジャッジ時間 23,482 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 23 TLE * 5 -- * 57
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import deque

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    H = int(data[0])
    W = int(data[1])
    grid = data[2:]
    
    new_h = 2 * H - 1
    new_w = 2 * W - 1
    
    # We don't explicitly need to build the 2D array of the expanded grid.
    # We can determine if a coordinate is a wall '#' mathematically to save memory/time.
    # (r, c) represents coordinates in the expanded grid.
    def is_wall(r, c):
        if r % 2 == 0 and c % 2 == 0:
            return grid[r // 2][c // 2] == '#'
        return False

    dist = [[-1] * new_w for _ in range(new_h)]
    
    q = deque()
    q.append((0, 0))
    dist[0][0] = 0
    
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    
    while q:
        r, c = q.popleft()
        
        if r == new_h - 1 and c == new_w - 1:
            print(dist[r][c])
            return
            
        current_d = dist[r][c]
        
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            
            if 0 <= nr < new_h and 0 <= nc < new_w:
                if not is_wall(nr, nc):
                    if dist[nr][nc] == -1:
                        dist[nr][nc] = current_d + 1
                        q.append((nr, nc))
                        
    print(-1)

if __name__ == '__main__':
    solve()
0