結果

問題 No.3504 Insert Maze
コンテスト
ユーザー Nattt
提出日時 2026-04-17 23:38:24
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 4,927 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 719 ms
コンパイル使用メモリ 20,696 KB
実行使用メモリ 214,008 KB
最終ジャッジ日時 2026-04-17 23:39:40
合計ジャッジ時間 19,165 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 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:]
    
    HW = H * W
    HW2 = 2 * HW
    HW3 = 3 * HW
    
    dist = [-1] * (4 * HW)
    
    start_state = 0
    end_state = HW - 1
    
    q = deque([start_state])
    dist[start_state] = 0
    
    is_empty = [False] * HW
    for r in range(H):
        row_str = grid[r]
        base = r * W
        for c in range(W):
            if row_str[c] != '#':
                is_empty[base + c] = True

    q_popleft = q.popleft
    q_append = q.append
    
    while q:
        curr = q_popleft()
        if curr == end_state:
            print(dist[curr])
            return
            
        d = dist[curr]
        nd = d + 1
        
        typ = curr // HW
        rem = curr % HW
        r = rem // W
        c = rem % W
        
        if typ == 0:
            if r > 0:
                nxt = rem - W
                if is_empty[nxt] and dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
            if r < H - 1:
                nxt = rem + W
                if is_empty[nxt] and dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
            if c > 0:
                nxt = rem - 1
                if is_empty[nxt] and dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
            if c < W - 1:
                nxt = rem + 1
                if is_empty[nxt] and dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
                    
            if r < H - 1:
                nxt = HW + rem
                if dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
            if r > 0:
                nxt = HW + rem - W
                if dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
                    
            if c < W - 1:
                nxt = HW2 + rem
                if dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
            if c > 0:
                nxt = HW2 + rem - 1
                if dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
                    
        elif typ == 1:
            if is_empty[rem] and dist[rem] == -1:
                dist[rem] = nd
                q_append(rem)
            nxt = rem + W
            if is_empty[nxt] and dist[nxt] == -1:
                dist[nxt] = nd
                q_append(nxt)
                
            if c > 0:
                nxt = curr - 1
                if dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
            if c < W - 1:
                nxt = curr + 1
                if dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
                    
            if c < W - 1:
                nxt = HW3 + rem
                if dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
            if c > 0:
                nxt = HW3 + rem - 1
                if dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
                    
        elif typ == 2:
            if is_empty[rem] and dist[rem] == -1:
                dist[rem] = nd
                q_append(rem)
            nxt = rem + 1
            if is_empty[nxt] and dist[nxt] == -1:
                dist[nxt] = nd
                q_append(nxt)
                
            if r > 0:
                nxt = curr - W
                if dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
            if r < H - 1:
                nxt = curr + W
                if dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
                    
            if r < H - 1:
                nxt = HW3 + rem
                if dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
            if r > 0:
                nxt = HW3 + rem - W
                if dist[nxt] == -1:
                    dist[nxt] = nd
                    q_append(nxt)
                    
        else:
            nxt = HW + rem
            if dist[nxt] == -1:
                dist[nxt] = nd
                q_append(nxt)
            nxt = HW + rem + 1
            if dist[nxt] == -1:
                dist[nxt] = nd
                q_append(nxt)
                
            nxt = HW2 + rem
            if dist[nxt] == -1:
                dist[nxt] = nd
                q_append(nxt)
            nxt = HW2 + rem + W
            if dist[nxt] == -1:
                dist[nxt] = nd
                q_append(nxt)

    print(-1)

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