AtCoder が提供しているABC(AtCoder Beginner Contest)387 D問題をC++とPythonで解いてみました。ABC387は、2025年1月4日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Snaky Walk(Difficulty : 817)
問題の詳細は、リンク先をご覧ください。
移動方向に制約がある迷路の最短経路を求める問題です。AtCoder Problems による Difficulty は 817 でした。
解答案
グリッド(迷路)の最短距離を求める問題について、
【定番コード】BFSで迷路の最短距離を求める。
でまとめていました。
グリッド移動の最短距離を求める問題ですが、縦→横→縦→横→...または、横→縦→横→縦→...となる2通りについて調べます。
C++ プログラム例(ABC387D)
上で紹介した定番コードをベースにします。
グリッドの移動方向を表す配列 di
、dj
を用いて、分がいるマスが偶数距離か奇数距離かによって使用する方向を決めます。先に横→縦となる場合(i=0
)を調べ、次に縦→横となる場合(i=1
)を調べて、その最短距離を出力します。
以下が、C++プログラムです。ポイントとなるコードの背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
int main()
{
int h, w;
cin >> h >> w;
vector<string> s(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
int si = -1;
int sj = -1;
int gi = -1;
int gj = -1;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (s[i][j] == 'S') {
si = i;
sj = j;
}
if (s[i][j] == 'G') {
gi = i;
gj = j;
}
}
}
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
int result = INF;
for (int i = 0; i < 2; ++i) {
queue<pair<int, int>> que;
vector<vector<int>> dist(h, vector(w, -1));
que.push(make_pair(si, sj));
dist[si][sj] = 0;
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 ((dist[now_i][now_j] % 2 == 0) && (d % 2 == i)) {
continue;
}
if ((dist[now_i][now_j] % 2 == 1) && (d % 2 == (i + 1) % 2)) {
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][next_j] == -1) &&
(s[next_i][next_j] != '#')) {
que.push(make_pair(next_i, next_j));
dist[next_i][next_j] = dist[now_i][now_j] + 1;
}
}
}
if (dist[gi][gj] != -1) {
result = min(result, dist[gi][gj]);
}
}
if (result == INF) {
result = -1;
}
cout << result << endl;
return 0;
}
AC(Accepted=正しいプログラム)と判定されました。
Python プログラム例(ABC387D)
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 387 D"""
from collections import deque
INF = 1 << 30
h, w = map(int, input().split())
s = [input() for i in range(h)]
si = -1
sj = -1
gi = -1
gj = -1
for i in range(h):
for j in range(w):
if s[i][j] == 'S':
si = i
sj = j
if s[i][j] == 'G':
gi = i
gj = j
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
result = INF
for i in range(2):
que = deque()
dist = [[-1 for _ in range(w)] for _ in range(h)]
que.append((si, sj))
dist[si][sj] = 0
while que:
now = que.popleft()
now_i = now[0]
now_j = now[1]
for d in range(4):
if dist[now_i][now_j] % 2 == 0 and d % 2 == i:
continue
if dist[now_i][now_j] % 2 == 1 and d % 2 == (i + 1) % 2:
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 s[next_i][next_j] != '#':
que.append((next_i, next_j))
dist[next_i][next_j] = dist[now_i][now_j] + 1
if dist[gi][gj] != -1:
result = min(result, dist[gi][gj])
if result == INF:
result = -1
print(result)
こちらも「AC」と判定されました。
最後に
グリッドを BFS で処理する問題に慣れていたため、コンテストで解くことができました。
引き続き ABC の問題を紹介していきます。