AtCoder が提供しているABC（AtCoder Beginner Contest）276 のE問題をC++とPythonで解いてみました。ABC276は、2022年11月5日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Round Trip（Difficulty : 1058）
問題はリンク先をご覧ください。
最初に動ける場所からBFSを用いて、スタート地点への距離を求めます。AtCoder Problems による Difficulty は、1058 でした。
解答案
スタート地点から長さが4以上の経路で戻れるか判定します。
もし、長さが2であれば簡単です。スタート地点から上下左右の隣のマスに移動できれば、次にスタート地点に戻れば長さ2の経路で戻ることができます。
逆にこれ以外の経路では、長さが必ず4以上になります。これは、行きと戻りの移動回数を縦軸と横軸に分ければ、どちらも偶数回になるためです。
問題を以下のように言い換えることができます。
- スタート地点の上下左右のマスから、すぐにスタート地点に戻る以外の経路で
- スタート地点に戻る経路があるか？
C++ プログラム例（ABC276E）
言い換えた問題を実装します。プログラムでは、距離の配列 dist の添え字を1次元に変換して処理しています。
- スタート地点の上下左右のマスから到達しているマスを調べる関数を分けました。与えられたマスを始点としてBFSで探索します（10ー39行目）。
- 指定された地点をキューに格納して、その距離 dist を1に設定する。
- キューに要素がある限り、以下を行う。
- 最初の移動で、指定された方向と一致している場合は次を探す（24ー27行目）。
- その地点から4方向に移動して空きマスでまだ到達していなければ、その地点をキューに格納して（34行目）、距離 dist を更新する（35行目）。
- 関数 main では以下の処理を行います。
- 読み込んだ文字列からスタート地点を探す。地図のマスを ‘.’ に変更する（49ー58行目）。
- 上下左右の4方向について、以下の操作を行います。それぞれの方向の移動は配列 di と dj で定義しておきます（7、8行目）。
- スタート地点から隣のマスが ‘.’ であれば、その地点と距離、戻る方向を指定して関数 bfs を呼び出す（68行目）。
- 関数 bfs から戻ってきて、スタート地点の移動距離が -1 以外であれば、目的となっている経路が見つかったことを表します。
以下が、C＋＋プログラムとなります。少し長くなりました。ポイントとなる行の背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
int h, w;
vector<string> c;
vector<int> dist;
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
void bfs(int i, int j, vector<int> &dist, int direction)
{
queue<pair<int, int>> que;
bool is_first = true;
que.push(make_pair(i, j));
dist[i * w + j] = 1;
while (!que.empty()) {
pair<int, int> now = que.front();
que.pop();
int now_i = now.first;
int now_j = now.second;
for (int d = 0; d < 4; ++d) {
if (is_first &&(d == direction)) {
is_first = false;
continue;
}
int next_i = now_i + di[d];
int next_j = now_j + dj[d];
if ((0 <= next_i)&&(next_i < h)
&&(0 <= next_j)&&(next_j < w)
&&(dist[next_i * w + next_j] == -1)
&&(c[next_i][next_j] == '.')) {
que.push(make_pair(next_i, next_j));
dist[next_i * w + next_j] = dist[now_i * w + now_j] + 1;
}
}
}
}
int main()
{
cin >> h >> w;
c.resize(h);
for (int i = 0; i < h; ++i) {
cin >> c[i];
}
int si, sj;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (c[i][j] == 'S') {
si = i;
sj = j;
c[si][sj] = '.';
}
}
}
bool result = false;
for (int d = 0; d < 4; ++d) {
dist.assign(h * w, -1);
int next_i = si + di[d];
int next_j = sj + dj[d];
if ((0 <= next_i)&&(next_i < h)
&&(0 <= next_j)&&(next_j < w)
&&(c[next_i][next_j] == '.')) {
bfs(next_i, next_j, dist, (d + 2) % 4);
if (dist[si * w + sj] != -1) {
result = true;
break;
}
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}このプログラムは、AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC276E）
Python 版も基本的な考え方は同じです。キューは deque を使います。以下となります。
"""AtCoder Beginner Contest 276 E"""
from collections import deque
def bfs(i, j, direction):
global di, dj, h, w, c, dist
is_first = True
que = deque()
que.append((i, j))
dist[i][j] = 1
while que:
now_i, now_j = que.popleft()
for d in range(4):
if is_first and d == direction:
is_first = False
continue
next_i = now_i + di[d]
next_j = now_j + dj[d]
if 0 <= next_i < h and 0 <= next_j < w and \
dist[next_i][next_j] == -1 and c[next_i][next_j] == '.':
que.append((next_i, next_j))
dist[next_i][next_j] = dist[now_i][now_j] + 1
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
h, w = map(int, input().split())
c = [list(input()) for i in range(h)]
for i in range(h):
for j in range(w):
if c[i][j] == 'S':
si = i
sj = j
c[si][sj] = '.'
result = False
for d in range(4):
dist = [[-1 for _ in range(w)] for _ in range(h)]
next_i = si + di[d]
next_j = sj + dj[d]
if 0 <= next_i < h and 0 <= next_j < w and c[next_i][next_j] == '.':
bfs(next_i, next_j, (d + 2) % 4)
if dist[si][sj] != -1:
result = True
break
print("Yes" if result else "No")こちらも「AC」と判定されました。
最後に
この問題は、コンテスト参加時には解くことができませんでした。BFSに慣れてきて解くことができたため、記事として紹介しました。
引き続き ABC の問題を紹介していきます。
