結果

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

ソースコード

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:]
    
    # Types of states:
    # 0: In a regular grid cell (r, c)
    # 1: On a horizontal highway between row r and r+1, at column c
    # 2: On a vertical highway between col c and c+1, at row r
    # 3: At the intersection of horizontal highway r and vertical highway c
    
    # We flatten the states into a 1D array to optimize Python array access times
    # state_id = (r * W + c) * 4 + type
    num_states = H * W * 4
    dist = [-1] * num_states
    
    start_state = 0 # (0, 0, 0)
    dist[start_state] = 0
    
    dq = deque([start_state])
    
    while dq:
        u = dq.popleft()
        d_u = dist[u]
        
        type_ = u % 4
        rem = u // 4
        c = rem % W
        r = rem // W
        
        if r == H - 1 and c == W - 1 and type_ == 0:
            print(d_u)
            return
            
        # Helper to push states into the deque
        def push(nr, nc, ntype, cost):
            nu = (nr * W + nc) * 4 + ntype
            if dist[nu] == -1 or dist[nu] > d_u + cost:
                dist[nu] = d_u + cost
                if cost == 0:
                    dq.appendleft(nu)
                else:
                    dq.append(nu)

        if type_ == 0:
            # Type 0: Normal Grid Cell
            # Move to adjacent normal cells
            if r > 0 and grid[r - 1][c] != '#': push(r - 1, c, 0, 1)
            if r < H - 1 and grid[r + 1][c] != '#': push(r + 1, c, 0, 1)
            if c > 0 and grid[r][c - 1] != '#': push(r, c - 1, 0, 1)
            if c < W - 1 and grid[r][c + 1] != '#': push(r, c + 1, 0, 1)
            
            # Enter Highways
            if r < H - 1: push(r, c, 1, 1)     # Below
            if r > 0: push(r - 1, c, 1, 1)     # Above
            if c < W - 1: push(r, c, 2, 1)     # Right
            if c > 0: push(r, c - 1, 2, 1)     # Left

        elif type_ == 1:
            # Type 1: Horizontal Highway
            # Leave highway
            push(r, c, 0, 1)
            push(r + 1, c, 0, 1)
            
            # Move along highway
            if c > 0: push(r, c - 1, 1, 1)
            if c < W - 1: push(r, c + 1, 1, 1)
            
            # Enter intersections
            if c < W - 1: push(r, c, 3, 1)
            if c > 0: push(r, c - 1, 3, 1)

        elif type_ == 2:
            # Type 2: Vertical Highway
            # Leave highway
            push(r, c, 0, 1)
            push(r, c + 1, 0, 1)
            
            # Move along highway
            if r > 0: push(r - 1, c, 2, 1)
            if r < H - 1: push(r + 1, c, 2, 1)
            
            # Enter intersections
            if r < H - 1: push(r, c, 3, 1)
            if r > 0: push(r - 1, c, 3, 1)

        elif type_ == 3:
            # Type 3: Intersection
            # Leave intersection
            push(r, c, 1, 1)
            push(r, c + 1, 1, 1)
            push(r, c, 2, 1)
            push(r + 1, c, 2, 1)

    print("-1")

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