結果

問題 No.3504 Insert Maze
コンテスト
ユーザー Qiu Tian
提出日時 2026-04-18 20:06:02
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WA  
実行時間 -
コード長 4,327 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 335 ms
コンパイル使用メモリ 20,700 KB
実行使用メモリ 202,744 KB
最終ジャッジ日時 2026-04-18 20:07:32
合計ジャッジ時間 17,571 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_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_data = sys.stdin.read().split()
    if not input_data:
        return
    
    H = int(input_data[0])
    W = int(input_data[1])
    grid = input_data[2:]
    
    # 状態:
    # 0 = 通常のマス (r, c)
    # 1 = 行 r と r+1 の間の挿入行 (横移動用)
    # 2 = 列 c と c+1 の間の挿入列 (縦移動用)
    
    # 距離配列を1次元配列にして高速化 (3 * H * W)
    # インデックス: state * (H * W) + r * W + c
    INF = 10**9
    dist = [INF] * (3 * H * W)
    
    start_idx = 0  # state=0, r=0, c=0
    dist[start_idx] = 0
    
    q = deque([start_idx])
    
    # 事前に壁でないかを判定する補助リスト (高速化のため)
    is_valid = [[grid[r][c] != '#' for c in range(W)] for r in range(H)]
    
    HW = H * W
    
    while q:
        curr = q.popleft()
        d = dist[curr]
        
        state = curr // HW
        rem = curr % HW
        r = rem // W
        c = rem % W
        
        # ゴール判定
        if state == 0 and r == H - 1 and c == W - 1:
            print(d)
            return

        nd = d + 1

        if state == 0:
            # 1. 通常マスの上下左右移動
            if r > 0 and is_valid[r-1][c]:
                nxt = (r - 1) * W + c
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)
            if r + 1 < H and is_valid[r+1][c]:
                nxt = (r + 1) * W + c
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)
            if c > 0 and is_valid[r][c-1]:
                nxt = r * W + (c - 1)
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)
            if c + 1 < W and is_valid[r][c+1]:
                nxt = r * W + (c + 1)
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)
            
            # 2. 挿入行・列に入る
            # 行rの下に挿入された行へ
            if r + 1 < H:
                nxt = HW + r * W + c
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)
            # 行rの上に挿入された行へ (行r-1の下という扱い)
            if r > 0:
                nxt = HW + (r - 1) * W + c
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)
                
            # 列cの右に挿入された列へ
            if c + 1 < W:
                nxt = 2 * HW + r * W + c
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)
            # 列cの左に挿入された列へ (列c-1の右という扱い)
            if c > 0:
                nxt = 2 * HW + r * W + (c - 1)
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)

        elif state == 1:
            # state=1 は 行rとr+1の間の通路 (横移動)
            # 左右の同一直線上(挿入行内)を移動
            if c > 0:
                nxt = HW + r * W + (c - 1)
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)
            if c + 1 < W:
                nxt = HW + r * W + (c + 1)
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)
            
            # 元のグリッド (上の行r または 下の行r+1) に戻る
            if is_valid[r][c]:
                nxt = r * W + c
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)
            if is_valid[r+1][c]:
                nxt = (r + 1) * W + c
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)

        elif state == 2:
            # state=2 は 列cとc+1の間の通路 (縦移動)
            # 上下の同一直線上(挿入列内)を移動
            if r > 0:
                nxt = 2 * HW + (r - 1) * W + c
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)
            if r + 1 < H:
                nxt = 2 * HW + (r + 1) * W + c
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)
            
            # 元のグリッド (左の列c または 右の列c+1) に戻る
            if is_valid[r][c]:
                nxt = r * W + c
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)
            if is_valid[r][c+1]:
                nxt = r * W + (c + 1)
                if dist[nxt] > nd: dist[nxt] = nd; q.append(nxt)

    print(-1)

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