結果

問題 No.3504 Insert Maze
コンテスト
ユーザー Qiu Tian
提出日時 2026-04-18 20:02:00
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WA  
実行時間 -
コード長 4,177 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 509 ms
コンパイル使用メモリ 20,700 KB
実行使用メモリ 74,152 KB
最終ジャッジ日時 2026-04-18 20:03:19
合計ジャッジ時間 23,334 ms
ジャッジサーバーID
（参考情報） 		judge3_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 = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    H = int(data[0])
    W = int(data[1])
    grid = data[2:]
    
    # 頂点の状態を拡張:
    # 0: 通常のマスにいる
    # 1: 挿入された行 (縦方向に自由に動ける通路の横移動中) にいる
    # 2: 挿入された列 (横方向に自由に動ける通路の縦移動中) にいる
    
    # 距離配列
    INF = float('inf')
    dist = [[[INF] * W for _ in range(H)] for _ in range(3)]
    
    # deque (cost, state, r, c)
    q = deque()
    
    # スタート地点
    dist[0][0][0] = 0
    q.append((0, 0, 0, 0))
    
    # 移動方向 (上下左右)
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    
    while q:
        d, state, r, c = q.popleft()
        
        if d > dist[state][r][c]:
            continue
            
        if r == H - 1 and c == W - 1 and state == 0:
            print(d)
            return

        # 状態 0: 通常のマス
        if state == 0:
            # 1. 通常の移動 (隣接するマスへ)
            for i in range(4):
                nr, nc = r + dr[i], c + dc[i]
                if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] != '#':
                    if dist[0][nr][nc] > d + 1:
                        dist[0][nr][nc] = d + 1
                        q.append((d + 1, 0, nr, nc))
            
            # 2. 挿入された行に入る (下向きに挿入された行があるとする)
            if r + 1 < H:
                if dist[1][r][c] > d + 1:
                    dist[1][r][c] = d + 1
                    q.append((d + 1, 1, r, c))
            # 挿入された行に入る (上向き)
            if r - 1 >= 0:
                if dist[1][r - 1][c] > d + 1:
                    dist[1][r - 1][c] = d + 1
                    q.append((d + 1, 1, r - 1, c))
                    
            # 3. 挿入された列に入る (右向き)
            if c + 1 < W:
                if dist[2][r][c] > d + 1:
                    dist[2][r][c] = d + 1
                    q.append((d + 1, 2, r, c))
            # 挿入された列に入る (左向き)
            if c - 1 >= 0:
                if dist[2][r][c - 1] > d + 1:
                    dist[2][r][c - 1] = d + 1
                    q.append((d + 1, 2, r, c - 1))
        
        # 状態 1: 挿入された行にいる場合
        elif state == 1:
            # 1. 同じ挿入行内を左右に移動
            for nc in [c - 1, c + 1]:
                if 0 <= nc < W:
                    if dist[1][r][nc] > d + 1:
                        dist[1][r][nc] = d + 1
                        q.append((d + 1, 1, r, nc))
            
            # 2. 元のグリッド (上下の行のどちらか) に戻る
            for nr in [r, r + 1]: # r は挿入行のすぐ上の行インデックス
                if 0 <= nr < H and grid[nr][c] != '#':
                    if dist[0][nr][c] > d + 1:
                        dist[0][nr][c] = d + 1
                        q.append((d + 1, 0, nr, c))
                        
            # (挿入された行から別の挿入された列へ直接移ることは、交差点が通路になるため可能ですが
            #  一度通常マスを介すのと同等なので省略可能)

        # 状態 2: 挿入された列にいる場合
        elif state == 2:
            # 1. 同じ挿入列内を上下に移動
            for nr in [r - 1, r + 1]:
                if 0 <= nr < H:
                    if dist[2][nr][c] > d + 1:
                        dist[2][nr][c] = d + 1
                        q.append((d + 1, 2, nr, c))
            
            # 2. 元のグリッド (左右の列のどちらか) に戻る
            for nc in [c, c + 1]: # c は挿入列のすぐ左の列インデックス
                if 0 <= nc < W and grid[r][nc] != '#':
                    if dist[0][r][nc] > d + 1:
                        dist[0][r][nc] = d + 1
                        q.append((d + 1, 0, r, nc))

    # ゴールに到達できない場合
    print(-1)

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