ABC339 D - Synchronized Players

atcoder.jp

問題

• $N\times N$のグリッド板があるよ
• 各マスは、空きマス、障害物のどちらかだよ
• プレイヤーのコマが盤上に2つ存在するよ
• 板を上に傾けると、プレイヤーのコマが同時に1マス上に移動しようとするよ
  • 移動先が障害物なら、そのプレイヤーは動けないよ
    • 両方動く場合も、片方だけ動く場合もあるよ
  • 右、左、下に関しても同じだよ
• プレイヤーのコマを同じマスに集めたいよ。最小手数を教えてね

成約

• $2 \leq N \leq 2\times 60$
• プレイヤーのコマは2つ

思考

• 終わり盤面から見ていこうとした時点で負け確定
• 成約が小さいので、全部の情報を盛り込んじゃえばどうにでもなる話だった
• 盤面は$60 \times 60$なので、最大3600マス
• プレイヤー1が存在する場所は高々3600マス、プレイヤー2も同様
  • $ 3600 \times 3600 = 12,960,000$
• (プレイヤー1の場所、プレイヤー2の場所)を持って、初期盤面から何手かかる？のBFSで終わり
• これが解けなかったのは、とても、つらい…

コード

from collections import deque

N = int(input())
grid_L = []
for i in range(N):
    S = input()
    grid_L += list(S)

P_L = []
for i in range(N):
    for j in range(N):
        if grid_L[i*N+j] == "P":
            P_L.append((i*N+j))

ans_L = [-1]*(N*N*N*N)
ans_L[P_L[0]*(N*N)+P_L[1]] = ans_L[P_L[1]*(N*N)+P_L[0]] = 0
dir = [-N,1,N,-1]
que = deque([P_L[0]*(N*N)+P_L[1],P_L[1]*(N*N)+P_L[0]])

while que:
    status = que.popleft()
    now_score = ans_L[status]
    p1 = status // (N*N)
    p2 = status % (N*N)

    if p1 == p2:
        print(now_score)
        exit()

    for d in dir:

        if 0 <= p1+d < N*N and grid_L[p1+d] != "#" and (p1 % N == (p1+d) % N or p1//N == (p1+d) // N):
            np1 = p1+d
        else:
            np1 = p1
        if 0 <= p2+d < N*N and grid_L[p2+d] != "#" and (p2 % N == (p2+d) % N or p2//N == (p2+d) // N):
            np2 = p2+d
        else:
            np2 = p2
        if ans_L[np1*(N*N)+np2] == -1:
            ans_L[np1*(N*N)+np2] = now_score + 1
            que.append(np1*(N*N)+np2)
        if ans_L[np2*(N*N)+np1] == -1:
            ans_L[np2*(N*N)+np1] = now_score + 1
            que.append(np2*(N*N)+np1)

print(-1)