結果

問題 No.3504 Insert Maze
コンテスト
ユーザー はじっこゆーれー
提出日時 2026-04-18 00:27:57
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 4,472 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 524 ms
コンパイル使用メモリ 20,956 KB
実行使用メモリ 120,164 KB
最終ジャッジ日時 2026-04-18 00:29:43
合計ジャッジ時間 24,647 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26 TLE * 2 -- * 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_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
    while head < tail:
        u = q[head]
        head += 1
        d = distS[u] + 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 % W != 0:
            v = u - 1
            if distS[v] == INF and grid_str[v] != '#':
                distS[v] = d
                q[tail] = v
                tail += 1
        if (u + 1) % W != 0:
            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
        
        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 % W != 0:
            v = u - 1
            if distG[v] == INF and grid_str[v] != '#':
                distG[v] = d
                q[tail] = v
                tail += 1
        if (u + 1) % W != 0:
            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

    # Check horizontal insertions (row insertions)
    for r in range(H - 1):
        idx1 = r * W
        idx2 = idx1 + W
        
        S0 = distS[idx1 : idx1 + W]
        S1 = distS[idx2 : idx2 + W]
        G0 = distG[idx1 : idx1 + W]
        G1 = distG[idx2 : idx2 + W]
        
        for S_arr in (S0, S1):
            for G_arr in (G0, G1):
                res = INF
                min_S = INF
                for i in range(W):
                    s_val = S_arr[i] - i
                    if s_val < min_S:
                        min_S = s_val
                    val = min_S + G_arr[i] + i
                    if val < res:
                        res = val
                    
                min_S = INF
                for i in range(W - 1, -1, -1):
                    s_val = S_arr[i] + i
                    if s_val < min_S:
                        min_S = s_val
                    val = min_S + G_arr[i] - i
                    if val < res:
                        res = val
                    
                res += 2
                if res < ans:
                    ans = res

    # Check vertical insertions (column insertions)
    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]
        
        for S_arr in (S0, S1):
            for G_arr in (G0, G1):
                res = INF
                min_S = INF
                for i in range(H):
                    s_val = S_arr[i] - i
                    if s_val < min_S:
                        min_S = s_val
                    val = min_S + G_arr[i] + i
                    if val < res:
                        res = val
                    
                min_S = INF
                for i in range(H - 1, -1, -1):
                    s_val = S_arr[i] + i
                    if s_val < min_S:
                        min_S = s_val
                    val = min_S + G_arr[i] - i
                    if val < res:
                        res = val
                    
                res += 2
                if res < ans:
                    ans = res

    print(ans)

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