AtCoder が提供しているABC（AtCoder Beginner Contest）317 のE問題をC++とPythonで解いてみました。ABC317は、2023年8月26日21:00に実施されました。
ABC316は欠番になりました。AtCoderからのお知らせはこちらです。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Avoid Eye Contact（Difficulty : 1085）
問題はリンク先をご覧ください。
人の視線を前処理して、BFSで迷路探索を行います。AtCoder Problems による Difficulty は 1085 でした。
解答案
人とその視線が無ければ、典型的な迷路の最短距離を求める問題です。BFS（キュー）の例題としてよく紹介されています。
この問題の場合、人の視線を障害物と考えて、視線を前処理します。前処理した後の迷路は、前述の典型問題を解く方法で解くことができます。
実装上の工夫は以下です。
- 4方向の処理を楽にするために移動量の配列 dx と dy を定義して使います。これによって、4方向への処理を繰り返し文で書くことができます。
- 視線は障害物（’#’）と区別するため ‘！’ を使いました。出力例1にある記述に合わせました。
C++ プログラム例（ABC317E）
すでに説明したように前処理と迷路探索の2つに分けます。
前処理では、すでに読み込んだ迷路を上書きして、視線がある場所を空きマスから ‘！’ に置き換えます。合わせて、スタート地点とゴール地点を読み込みます。ゴール地点は通常の探索範囲とするために空きマスに書き換えています（16ー50行目）。
迷路探索では、BFS（キュー）を使って各空きマスまでの最短距離を求めます（55ー74行目）。
最後にゴール地点の最短距離を出力します（76行目）。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w;
cin >> h >> w;
vector<string> a(h);
for (int i = 0; i < h; ++i) {
cin >> a[i];
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int sy, sx;
int gy, gx;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
int index = -1;
if (a[i][j] == '>') {
index = 0;
} else if (a[i][j] == 'v') {
index = 1;
} else if (a[i][j] == '<') {
index = 2;
} else if (a[i][j] == '^') {
index = 3;
} else if (a[i][j] == 'S') {
sy = i;
sx = j;
} else if (a[i][j] == 'G') {
a[i][j] = '.';
gy = i;
gx = j;
}
if (index >= 0) {
int next_x = j + dx[index];
int next_y = i + dy[index];
while ((0 <= next_x)&&(next_x < w)
&& (0 <= next_y)&&(next_y < h)
&& ((a[next_y][next_x] == '.')||(a[next_y][next_x] == '!'))) {
a[next_y][next_x] = '!';
next_x += dx[index];
next_y += dy[index];
}
}
}
}
queue<pair<int, int>> que;
vector<vector<int>> dist(h, vector<int>(w, -1));
que.push(make_pair(sx, sy));
dist[sy][sx] = 0;
while (!que.empty()) {
pair<int, int> now = que.front();
que.pop();
int now_x = now.first;
int now_y = now.second;
for (int i = 0; i < 4; ++i) {
int next_x = now_x + dx[i];
int next_y = now_y + dy[i];
if ((0 <= next_x)&&(next_x < w)
&&(0 <= next_y)&&(next_y < h)
&&(dist[next_y][next_x] == -1)
&&(a[next_y][next_x] == '.')) {
que.push(make_pair(next_x, next_y));
dist[next_y][next_x] = dist[now_y][now_x] + 1;
}
}
}
cout << dist[gy][gx] << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC317E）
Python も C＋＋ と同じ考え方で実装しました。補足は以下です。
- 文字列の要素を書き換えることができないため、文字列で読み込み、リストに変換しています（5ー9行目）。
- キューとして、collections モジュールの deque を使いました（2、41行目）。
以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。
"""AtCoder Beginner Contest 317 E"""
from collections import deque
h, w = map(int, input().split())
s = [input() for i in range(h)]
a = [["" for j in range(w)] for i in range(h)]
for i in range(h):
for j in range(w):
a[i][j] = s[i][j]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
for i in range(h):
for j in range(w):
index = -1
if a[i][j] == '>':
index = 0
elif a[i][j] == 'v':
index = 1
elif a[i][j] == '<':
index = 2
elif a[i][j] == '^':
index = 3
elif a[i][j] == 'S':
sx, sy = j, i
elif a[i][j] == 'G':
a[i][j] = '.'
gx, gy = j, i
if index >= 0:
next_x = j + dx[index]
next_y = i + dy[index]
while 0 <= next_x < w and \
0 <= next_y < h and \
(a[next_y][next_x] == '.' or a[next_y][next_x] == '!'):
a[next_y][next_x] = '!'
next_x += dx[index]
next_y += dy[index]
que = deque()
dist = [[-1 for j in range(w)] for i in range(h)]
que.append((sx, sy))
dist[sy][sx] = 0
while que:
now = que.popleft()
now_x = now[0]
now_y = now[1]
for i in range(4):
next_x = now_x + dx[i]
next_y = now_y + dy[i]
if 0 <= next_x < w and \
0 <= next_y < h and \
dist[next_y][next_x] == -1 and \
a[next_y][next_x] == '.':
que.append((next_x, next_y))
dist[next_y][next_x] = dist[now_y][now_x] + 1
print(dist[gy][gx])最後に
知っている範囲の典型問題だと分かり、B問題の次に解きました。ただし、解く途中に以下のミスをしていました。
- 視線の更新を空きマス（’.’）だけ行っていて視線（’！’）が先にあると処理できなかった（43行目の条件が足りない）。ロジックミスです。
- 迷路ゴール地点を ’G’ のまま処理していて、ゴールに到達していなかった（33行目が抜けていました）。広い意味でロジックのミスです。
結果的に41分でACしましたが、コンテストとしてはD問題を解くための時間が足りなくなりました。ABCのD問題やE問題が解けることが増えてきました。解く速さも改善していきたいです。
引き続き ABC の問題を紹介していきます。
