結果

問題 No.3504 Insert Maze
コンテスト
ユーザー Nattt
提出日時 2026-04-18 00:15:51
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 2,410 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 395 ms
コンパイル使用メモリ 20,696 KB
実行使用メモリ 50,508 KB
最終ジャッジ日時 2026-04-18 00:17:11
合計ジャッジ時間 15,885 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 TLE * 1 -- * 57
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

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:]
    
    R = 2 * H - 1
    C = 2 * W - 1
    
    R_prime = R + 4
    C_prime = C + 4
    N_prime = R_prime * C_prime
    
    visited = bytearray(b'\x01' * N_prime)
    
    empty_row = b'\x00' * C
    for r in range(R):
        start_idx = (r + 2) * C_prime + 2
        visited[start_idx : start_idx + C] = empty_row
        
    for r in range(H):
        row_str = grid[r]
        row_offset = (2 * r + 2) * C_prime
        for c in range(W):
            if row_str[c] == '#':
                visited[row_offset + 2 * c + 2] = 1
                
    can_jump_h = bytearray(N_prime)
    can_jump_v = bytearray(N_prime)
    
    row_ones = b'\x01' * C
    for r in range(0, R, 2):
        start_idx = (r + 2) * C_prime + 2
        can_jump_v[start_idx : start_idx + C] = row_ones
        
    for r in range(R):
        row_offset = (r + 2) * C_prime
        for c in range(0, C, 2):
            can_jump_h[row_offset + c + 2] = 1
            
    start = 2 * C_prime + 2
    target = (R - 1 + 2) * C_prime + (C - 1 + 2)
    
    if start == target:
        print(0)
        return
        
    q = [start]
    visited[start] = 1
    step = 1
    
    C_prime2 = 2 * C_prime
    
    while q:
        new_q = []
        app = new_q.append
        
        for u in q:
            v = u - 1
            if not visited[v]: visited[v] = 1; app(v)
            v = u + 1
            if not visited[v]: visited[v] = 1; app(v)
            v = u - C_prime
            if not visited[v]: visited[v] = 1; app(v)
            v = u + C_prime
            if not visited[v]: visited[v] = 1; app(v)
            
            if can_jump_h[u]:
                v = u - 2
                if not visited[v]: visited[v] = 1; app(v)
                v = u + 2
                if not visited[v]: visited[v] = 1; app(v)
                
            if can_jump_v[u]:
                v = u - C_prime2
                if not visited[v]: visited[v] = 1; app(v)
                v = u + C_prime2
                if not visited[v]: visited[v] = 1; app(v)
                
        if visited[target]:
            print(step)
            return
            
        q = new_q
        step += 1
        
    print(-1)

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