結果

問題 No.3504 Insert Maze
コンテスト
ユーザー Nattt
提出日時 2026-04-17 23:44:57
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 2,695 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 457 ms
コンパイル使用メモリ 20,832 KB
実行使用メモリ 31,560 KB
最終ジャッジ日時 2026-04-17 23:46:26
合計ジャッジ時間 17,463 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    N = R * C
    
    # bytearray super cepat & hemat memori untuk Python
    visited = bytearray(N)
    
    # Pre-fill grid walls
    for r in range(H):
        row = grid[r]
        base = 2 * r * C
        for c in range(W):
            if row[c] == '#':
                visited[base + 2 * c] = 1
                
    target = N - 1
    if target == 0:
        print(0)
        return
        
    q = [0]
    visited[0] = 1
    step = 0
    
    C2 = 2 * C
    
    while q:
        step += 1
        new_q = []
        app = new_q.append
        
        for u in q:
            c = u % C
            r = u // C
            
            # 1-step moves (semua cell bisa geser pelan)
            if c > 0:
                nxt = u - 1
                if not visited[nxt]:
                    visited[nxt] = 1
                    app(nxt)
            if c < C - 1:
                nxt = u + 1
                if not visited[nxt]:
                    visited[nxt] = 1
                    app(nxt)
            if r > 0:
                nxt = u - C
                if not visited[nxt]:
                    visited[nxt] = 1
                    app(nxt)
            if r < R - 1:
                nxt = u + C
                if not visited[nxt]:
                    visited[nxt] = 1
                    app(nxt)
                    
            # 2-step jump horizontal (hanya untuk cell asli & lorong horizontal)
            if (c & 1) == 0:
                if c >= 2:
                    nxt = u - 2
                    if not visited[nxt]:
                        visited[nxt] = 1
                        app(nxt)
                if c < C - 2:
                    nxt = u + 2
                    if not visited[nxt]:
                        visited[nxt] = 1
                        app(nxt)
                        
            # 2-step jump vertical (hanya untuk cell asli & lorong vertikal)
            if (r & 1) == 0:
                if r >= 2:
                    nxt = u - C2
                    if not visited[nxt]:
                        visited[nxt] = 1
                        app(nxt)
                if r < R - 2:
                    nxt = u + C2
                    if not visited[nxt]:
                        visited[nxt] = 1
                        app(nxt)
                        
        if visited[target]:
            print(step)
            return
            
        q = new_q
        
    print(-1)

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