[Baekjoon] 13460. 仙丹脱出2[G 1]

📚 質問する

https://www.acmicpc.net/problem/13460

📖 に答える

10回移動します.では4方向は10回なので、4の10平方は100万くらいです.
他の関連の複雑さを考慮すると、時間が増加し、タイムアウトが発生する可能性があります.
そこで,最適化によりバックグラウンド追跡の数を減らして問題を解決する.
まず赤いボールと青いボールの座標を覚えます.ballsは2次元配列順に赤いボールと青いボールを入れます.
ボールの位置は単独で保管して移動します.
関数は3種類あります.

くみあわせかんすう

4方向に移動し、10番の鬼才を探索する.10日に移動し、10日を超えると終了します.

最適化のための探索は,すでに得られた結果よりも多くの場合に終了する.

4方向探索は,以前に移動した方向を覚え,同じ方向や反対方向を見ない場合である.

も逆方向に探索しない理由は、以前とは逆方向に移動した場合と同様である.

ボールの位置をコピーして保存します.その後、移動と戻りのプロセスを繰り返します.

青いボールが落ちた場合、赤いボールが落ちた場合、両方とも落ちた場合に分けて分割処理します.

移動方向壁に近い球調和関数

ボールが同じ壁面に当たった場合は、まず近くのボールを貼ってから別のボールを貼るので、ボールが壁面に近いかどうかを確認する関数を作ります.

方向の値に座標を乗じると、移動方向の大きさの値が得られることが考えられます.この時、もっと大きな値段が壁に近い.

負数の場合、0に近い小さな値が現れるはずですが、負数に乗じて、小さな値が大きくなります.そのため、このように儀式を救うだけだ.

赤いボールがもっと近いときは1、または0を出力します.

特定の方向に傾斜したときにボールを移動する関数

ボールを移動します.壁や他のボールにぶつかると止まります.次に0を返します.

ホールに遭遇し、1を返します.このとき、ボールは-1,-1に送られます.両方がホールに入ることを確認しなければならないからです.そのため範囲外に送られた.

📒 コード#コード#

def recur(cur, prv_d):
    global cnt, balls
    if cnt <= cur:      # 이미 나온 결과보다 더 횟수가 많거나 같으면 종료
        return
    if cur == 10:       # 10번 넘게 움직였으면 종료
        return

    balls_origin = [balls[0][:], balls[1][:]]       # 공의 위치를 기억
    for d in range(4):
        balls = [balls_origin[0][:], balls_origin[1][:]]    # 공의 위치를 움직였으니 원상복구
        if prv_d >= 0 and (d % 2 == prv_d % 2):   # 같은 방향이거나 반대 방향인 경우는 보지 않는다.
            continue                            # 처음에만 방향을 -1로 설정해 모든 방향을 확인하도록 한다.
        if red_order(d):
            if move(0, d):  # 빨간 공이 빠지는 경우
                if move(1, d):  # 파란 공이 빠지는 경우
                    continue
                cnt = min(cur + 1, cnt)
                return
            if move(1, d):  # 파란 공이 빠지는 경우
                continue
        else:
            if move(1, d):  # 파란 공이 빠지는 경우
                continue
            if move(0, d):  # 빨간 공이 빠지는 경우
                cnt = min(cur + 1, cnt)
                return
        recur(cur + 1, d)
    

def red_order(dir):
    red_order = balls[0][0] * dx[dir] + balls[0][1] * dy[dir]
    blue_order = balls[1][0] * dx[dir] + balls[1][1] * dy[dir]
    if red_order >= blue_order:  # 빨간 공이 움직이는 방향의 벽에 더 가까이 있는 경우
        return 1
    else:
        return 0


def move(color, dir):    # 공 움직이기
    x, y = balls[color]     # 고른 공의 좌표
    x_another, y_another = balls[1^color] # 다른 색 공의 좌표
    while True:
        x += dx[dir]
        y += dy[dir]
        if arr[x][y] == '#' or (x == x_another and y == y_another):      # 벽을 만나는 경우 or 다른 색 공을 만난 경우
            balls[color][0] = x - dx[dir]
            balls[color][1] = y - dy[dir]
            return 0
        elif arr[x][y] == 'O':    # 골인 되는 경우
            balls[color][0] = -1
            balls[color][1] = -1
            return 1

dx = [0, 1, 0, -1]  # 우 하 좌 상
dy = [1, 0, -1, 0]
n, m = map(int, input().split())
arr = [list(input()) for _ in range(n)]
balls = [[], []]    # red, blue 공
for i in range(n):
    for j in range(m):
        if arr[i][j] == 'R':
            balls[0] = [i, j]
            arr[i][j] = '.'
        if arr[i][j] == 'B':
            balls[1] = [i, j]
            arr[i][j] = '.'

cnt = 11
recur(0, -1)

if cnt == 11:
    print(-1)
else:
    print(cnt)

🔍 結果