結果

問題 No.3504 Insert Maze
コンテスト
ユーザー はじっこゆーれー
提出日時 2026-04-18 00:41:25
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,345 ms / 2,000 ms
コード長 3,976 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 340 ms
コンパイル使用メモリ 85,248 KB
実行使用メモリ 257,372 KB
最終ジャッジ日時 2026-04-18 00:42:42
合計ジャッジ時間 43,704 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

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_str = "".join(input_data[2:])
    
    INF = 10**8
    N = H * W
    
    distS = [INF] * N
    distG = [INF] * N
    
    q = [0] * N
    
    # BFS from S
    head = 0
    tail = 1
    q[0] = 0
    distS[0] = 0
    
    Wm1 = W - 1
    while head < tail:
        u = q[head]
        head += 1
        d = distS[u] + 1
        u_c = u % W  # % 演算を1回に減らして高速化
        
        if u >= W:
            v = u - W
            if distS[v] == INF and grid_str[v] != '#':
                distS[v] = d
                q[tail] = v
                tail += 1
        if u < N - W:
            v = u + W
            if distS[v] == INF and grid_str[v] != '#':
                distS[v] = d
                q[tail] = v
                tail += 1
        if u_c != 0:
            v = u - 1
            if distS[v] == INF and grid_str[v] != '#':
                distS[v] = d
                q[tail] = v
                tail += 1
        if u_c != Wm1:
            v = u + 1
            if distS[v] == INF and grid_str[v] != '#':
                distS[v] = d
                q[tail] = v
                tail += 1

    # BFS from G
    head = 0
    tail = 1
    target = N - 1
    q[0] = target
    distG[target] = 0
    while head < tail:
        u = q[head]
        head += 1
        d = distG[u] + 1
        u_c = u % W
        
        if u >= W:
            v = u - W
            if distG[v] == INF and grid_str[v] != '#':
                distG[v] = d
                q[tail] = v
                tail += 1
        if u < N - W:
            v = u + W
            if distG[v] == INF and grid_str[v] != '#':
                distG[v] = d
                q[tail] = v
                tail += 1
        if u_c != 0:
            v = u - 1
            if distG[v] == INF and grid_str[v] != '#':
                distG[v] = d
                q[tail] = v
                tail += 1
        if u_c != Wm1:
            v = u + 1
            if distG[v] == INF and grid_str[v] != '#':
                distG[v] = d
                q[tail] = v
                tail += 1

    ans = distS[target]
    if H + W < ans:
        ans = H + W

    def check_insertion(S_in, G_out, length):
        res = INF
        min_S = INF
        for i in range(length):
            s_val = S_in[i] - i
            if s_val < min_S:
                min_S = s_val
            val = min_S + G_out[i] + i
            if val < res:
                res = val
                
        min_S = INF
        for i in range(length - 1, -1, -1):
            s_val = S_in[i] + i
            if s_val < min_S:
                min_S = s_val
            val = min_S + G_out[i] - i
            if val < res:
                res = val
                
        return res + 2

    # 行の挿入チェック
    for r in range(H - 1):
        idx1 = r * W
        idx2 = idx1 + W
        
        S0 = distS[idx1 : idx2]
        S1 = distS[idx2 : idx2 + W]
        G0 = distG[idx1 : idx2]
        G1 = distG[idx2 : idx2 + W]
        
        # S, G それぞれ
        S_in = [s0 if s0 < s1 else s1 for s0, s1 in zip(S0, S1)]
        G_out = [g0 if g0 < g1 else g1 for g0, g1 in zip(G0, G1)]
        
        res = check_insertion(S_in, G_out, W)
        if res < ans:
            ans = res

    # 列の挿入チェック
    S_cols = [distS[c::W] for c in range(W)]
    G_cols = [distG[c::W] for c in range(W)]
    
    for c in range(W - 1):
        S0 = S_cols[c]
        S1 = S_cols[c + 1]
        G0 = G_cols[c]
        G1 = G_cols[c + 1]
        
        S_in = [s0 if s0 < s1 else s1 for s0, s1 in zip(S0, S1)]
        G_out = [g0 if g0 < g1 else g1 for g0, g1 in zip(G0, G1)]
        
        res = check_insertion(S_in, G_out, H)
        if res < ans:
            ans = res

    print(ans)

if __name__ == '__main__': ##あとけす
    solve()
0