AtCoder が提供しているABC（AtCoder Beginner Contest）289 のE問題をC++とPythonで解いてみました。ABC289は、2023年2月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Swap Places（Difficulty : 1318）
問題はリンク先をご覧ください。
二人を組で考えて、BFSで最短距離を求めます。AtCoder Problems による Difficulty は 1318 でした。
解答案
高橋君と青木君のペアで考えて、以下の手順でキュー用いた探索（BFS）を行います。
- (1, N) を初期値として、キューに格納する。距離 dist(1, N) を0にします。このとき、前の数字は高橋君がいる頂点、二番目の数字は青木君がいる頂点です。
- 二人がいる頂点から移動できるすべての頂点の組で、二人が移動する頂点の色が異なる場合にキューに格納して、距離 dist を更新します。
- dist(N, 1) が求める答えになります。もし、dist(N, 1) が初期値のままなら到達しません。
C++ プログラム例（ABC289E）
この問題は、グラフが異なる $T$ 回のケースについて調べます。ただし、以下の制約があるため、それぞれのグラフは、あまり大きくなりません。
- 全てのテストケースに対する N の総和は 2000 を超えない。
- 全てのテストケースに対する M の総和は 2000 を超えない。
それぞれのケースで、グラフを読み込みます（9ー22行目）。上で述べた手順に従い、BFSで処理をします（24ー41行目）。
以下が、最終的な C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for (int test = 0; test < t; ++test) {
int n, m;
cin >> n >> m;
vector<int> c(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> c[i];
}
vector<vector<int>> G(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
vector<vector<int>> dist(n + 1, vector<int>(n + 1, -1));
queue<pair<int, int>> que;
que.push(make_pair(1, n));
dist[1][n] = 0;
while (!que.empty()) {
auto now = que.front();
que.pop();
int now_t = now.first;
int now_a = now.second;
for (auto next_t : G[now_t]) {
for (auto next_a : G[now_a]) {
if ((dist[next_t][next_a] == -1)&&(c[next_t] != c[next_a])) {
que.push(make_pair(next_t, next_a));
dist[next_t][next_a] = dist[now_t][now_a] + 1;
}
}
}
}
cout << dist[n][1] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC289E）
Python 版も基本的な考え方は同じです。キューは、collections.deque を使いました。以下となります。
"""AtCoder Beginner Contest 289 E"""
from collections import deque
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
c = list(map(int, input().split()))
c.insert(0, 0)
G = [[] for _ in range(n + 1)]
for _ in range(m):
u, v = map(int, input().split())
G[u].append(v)
G[v].append(u)
dist = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
que = deque()
que.append((1, n))
dist[1][n] = 0
while que:
now_t, now_a = que.popleft()
for next_t in G[now_t]:
for next_a in G[now_a]:
if dist[next_t][next_a] == -1 and c[next_t] != c[next_a]:
que.append((next_t, next_a))
dist[next_t][next_a] = dist[now_t][now_a] + 1
print(dist[n][1])どちらも「AC」と判定されました。
最後に
コンテストの開催順は前後しますが、ABC339D問題（解説記事）が類題となります。BFSで最短距離を求めるという意味では、よく出る問題なのかもしれません。
引き続き ABC の問題を紹介していきます。
