AtCoder が提供しているABC（AtCoder Beginner Contest）339 のD問題をC++とPythonで解いてみました。ABC339は、2024年2月3日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Synchronized Players（Difficulty : 1276）
問題はリンク先をご覧ください。
ABC339 D問題 Synchronized Players
二人の座標を組にしてBFSで距離を求めます。AtCoder Problems による Difficulty は 174 でした。
解答案
プレイヤーが一人であれば、典型的なBFSを使う問題です。
プレイヤーが二人ですが、二人の4次元の座標をキューに格納することによって、一人の場合と同じようなBFSで処理をします。最後に (i, j, i, j) と一人目と二人目が同じ座標になっている距離の最小値を求めます。
C++ プログラム例（ABC339D）
上記のアイデアをコードにします。二人の座標を組にしてBFSの初期値とします（40ー45行目）。二人の座標を左右上下に移動することが可能ならば、初期値との距離を確定して、キューに格納します（76ー79行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
int main()
{
int n;
cin >> n;
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
vector<pair<int, int>> p;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (s[i][j] == 'P') {
s[i][j] = '.';
p.push_back(make_pair(i, j));
}
}
}
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
queue<pair<pair<int, int>, pair<int, int>>> que;
int dist[n][n][n][n];
for (int i1 = 0; i1 < n; ++i1) {
for (int j1 = 0; j1 < n; ++j1) {
for (int i2 = 0; i2 < n; ++i2) {
for (int j2 = 0; j2 < n; ++j2) {
dist[i1][j1][i2][j2] = INF;
}
}
}
}
int i1 = p[0].first;
int j1 = p[0].second;
int i2 = p[1].first;
int j2 = p[1].second;
que.push(make_pair(make_pair(i1, j1), make_pair(i2, j2)));
dist[i1][j1][i2][j2] = 0;
while (!que.empty()) {
auto now = que.front();
que.pop();
for (int d = 0; d < 4; ++d) {
int now_i1 = now.first.first;
int now_j1 = now.first.second;
int next_i1 = now_i1 + di[d];
int next_j1 = now_j1 + dj[d];
if ((0 <= next_i1)&&(next_i1 < n)
&&(0 <= next_j1)&&(next_j1 < n)
&&(s[next_i1][next_j1] == '.')) {
i1 = next_i1;
j1 = next_j1;
} else {
i1 = now_i1;
j1 = now_j1;
}
int now_i2 = now.second.first;
int now_j2 = now.second.second;
int next_i2 = now_i2 + di[d];
int next_j2 = now_j2 + dj[d];
if ((0 <= next_i2)&&(next_i2 < n)
&&(0 <= next_j2)&&(next_j2 < n)
&&(s[next_i2][next_j2] == '.')) {
i2 = next_i2;
j2 = next_j2;
} else {
i2 = now_i2;
j2 = now_j2;
}
if (dist[i1][j1][i2][j2] == INF) {
dist[i1][j1][i2][j2] = dist[now_i1][now_j1][now_i2][now_j2] + 1;
que.push(make_pair(make_pair(i1, j1), make_pair(i2, j2)));
}
}
}
int result = INF;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
result = min(result, dist[i][j][i][j]);
}
}
if (result == INF) {
result = -1;
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC339D）
Python 版も基本的な考え方は同じです。キューは、collections.deque を使いました。
ただし、以下のプログラムは、「Python (CPython 3.11.4)」、「Python (PyPy 3.10-v7.3.12)」 共にTLE判定となりました。4次元ではなく2次元で処理するなどの工夫が必要なようです。
"""AtCoder Beginner Contest 339 D"""
from collections import defaultdict, deque
INF = 1 << 30
n = int(input())
s = [input() for i in range(n)]
p = []
for i in range(n):
for j in range(n):
if s[i][j] == 'P':
p.append((i, j))
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
que = deque()
dist = defaultdict(lambda: INF)
i1 = p[0][0]
j1 = p[0][1]
i2 = p[1][0]
j2 = p[1][1]
que.append((i1, j1, i2, j2))
dist[(i1, j1, i2, j2)] = 0
while que:
now = que.popleft()
for d in range(4):
now_i1 = now[0]
now_j1 = now[1]
next_i1 = now_i1 + di[d]
next_j1 = now_j1 + dj[d]
if 0 <= next_i1 < n and 0 <= next_j1 < n and s[next_i1][next_j1] != '#':
i1, j1 = next_i1, next_j1
else:
i1, j1 = now_i1, now_j1
now_i2 = now[2]
now_j2 = now[3]
next_i2 = now_i2 + di[d]
next_j2 = now_j2 + dj[d]
if 0 <= next_i2 < n and 0 <= next_j2 < n and s[next_i2][next_j2] != '#':
i2, j2 = next_i2, next_j2
else:
i2, j2 = now_i2, now_j2
if dist[(i1, j1, i2, j2)] == INF:
dist[(i1, j1, i2, j2)] = dist[(now_i1, now_j1, now_i2, now_j2)] + 1
que.append((i1, j1, i2, j2))
result = INF
for i in range(n):
for j in range(n):
result = min(result, dist[(i, j, i, j)])
if result == INF:
result = -1
print(result)こちらも「AC」と判定されました。
最後に
典型的なBFSで距離を求める問題を応用することによって解くことができる問題でした。コンテストでは解くことができませんでしたが、次に似たような問題がでたときに解ければと思います。
過去問ですが、ABC289E問題（解説記事）が類題となります。
引き続き ABC の問題を紹介していきます。
