結果

問題 No.3504 Insert Maze
コンテスト
ユーザー はじっこゆーれー
提出日時 2026-04-18 00:15:29
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WA  
実行時間 -
コード長 3,886 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 532 ms
コンパイル使用メモリ 20,828 KB
実行使用メモリ 77,028 KB
最終ジャッジ日時 2026-04-18 00:16:52
合計ジャッジ時間 19,212 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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_str = "".join(input_data[2:])
    
    C_off = 0
    HR_off = H * W
    VR_off = HR_off + (H - 1) * W
    I_off = VR_off + H * (W - 1)
    TOTAL_NODES = I_off + (H - 1) * (W - 1)
    
    dist = [-1] * TOTAL_NODES
    q = deque([0])
    dist[0] = 0
    target = H * W - 1
    
    Wm1 = W - 1
    Hm1 = H - 1
    
    q_popleft = q.popleft
    q_append = q.append
    
    while q:
        u = q_popleft()
        if u == target:
            print(dist[u])
            return
            
        nd = dist[u] + 1
        
        if u < HR_off:
            r, c = divmod(u, W)
            if r > 0:
                v = u - W
                if grid_str[v] != '#' and dist[v] == -1:
                    dist[v] = nd; q_append(v)
                v = HR_off + v
                if dist[v] == -1:
                    dist[v] = nd; q_append(v)
            if r < Hm1:
                v = u + W
                if grid_str[v] != '#' and dist[v] == -1:
                    dist[v] = nd; q_append(v)
                v = HR_off + u
                if dist[v] == -1:
                    dist[v] = nd; q_append(v)
            if c > 0:
                v = u - 1
                if grid_str[v] != '#' and dist[v] == -1:
                    dist[v] = nd; q_append(v)
                v = VR_off + u - r - 1
                if dist[v] == -1:
                    dist[v] = nd; q_append(v)
            if c < Wm1:
                v = u + 1
                if grid_str[v] != '#' and dist[v] == -1:
                    dist[v] = nd; q_append(v)
                v = VR_off + u - r
                if dist[v] == -1:
                    dist[v] = nd; q_append(v)
        elif u < VR_off:
            idx = u - HR_off
            r, c = divmod(idx, W)
            if dist[idx] == -1:
                dist[idx] = nd; q_append(idx)
            v = idx + W
            if dist[v] == -1:
                dist[v] = nd; q_append(v)
            if c > 0:
                v = u - 1
                if dist[v] == -1:
                    dist[v] = nd; q_append(v)
                v = I_off + idx - r - 1
                if dist[v] == -1:
                    dist[v] = nd; q_append(v)
            if c < Wm1:
                v = u + 1
                if dist[v] == -1:
                    dist[v] = nd; q_append(v)
                v = I_off + idx - r
                if dist[v] == -1:
                    dist[v] = nd; q_append(v)
        elif u < I_off:
            idx = u - VR_off
            r, c = divmod(idx, Wm1)
            v = idx + r
            if dist[v] == -1:
                dist[v] = nd; q_append(v)
            v += 1
            if dist[v] == -1:
                dist[v] = nd; q_append(v)
            if r > 0:
                v = u - Wm1
                if dist[v] == -1:
                    dist[v] = nd; q_append(v)
                v = I_off + idx - Wm1
                if dist[v] == -1:
                    dist[v] = nd; q_append(v)
            if r < Hm1:
                v = u + Wm1
                if dist[v] == -1:
                    dist[v] = nd; q_append(v)
                v = I_off + idx
                if dist[v] == -1:
                    dist[v] = nd; q_append(v)
        else:
            idx = u - I_off
            r, c = divmod(idx, Wm1)
            v = HR_off + idx + r
            if dist[v] == -1:
                dist[v] = nd; q_append(v)
            v += 1
            if dist[v] == -1:
                dist[v] = nd; q_append(v)
            v = VR_off + idx
            if dist[v] == -1:
                dist[v] = nd; q_append(v)
            v += Wm1
            if dist[v] == -1:
                dist[v] = nd; q_append(v)

    print(-1)

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