AtCoder が提供しているABC（AtCoder Beginner Contest）378 D問題をC++とPythonで解いてみました。ABC378は、2024年11月2日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Count Simple Paths（Difficulty : 587）
問題の詳細は、リンク先をご覧ください。
到達できるグリッドの距離をDFSで調べます。AtCoder Problems による Difficulty は 587 でした。
解答案
（グリッドではなく）グラフの問題ですが、ABC284E（解説記事）では、単純パス（同じ頂点を複数回通らないパス）の個数を求めています。この単純パスで長さが $K$ の個数を求める問題と考えることができます。※問題名もABC284Eと同じです。
グラフを対象としていますが、ABC284Eの再帰関数の実装は以下となります。
void dfs(int v)
{
++result;
seen[v] = true;
for (auto next_v : e[v]) {
if (!seen[next_v]) {
dfs(next_v);
}
}
seen[v] = false;
}グリッドを対象とすると以下となります。グラフの場合と考え方が同じですが、距離が $K$ の場合に result の値を増やしています。
void dfs(int i, int j, int depth)
{
if (depth == k) {
++result;
return;
}
seen[i][j] = true;
for (int d = 0; d < 4; ++d) {
int next_i = i + di[d];
int next_j = j + dj[d];
if ((0 <= next_i) && (next_i < h) && (0 <= next_j) &&
(next_j < w) && !seen[next_i][next_j] &&
(s[next_i][next_j] == '.')) {
dfs(next_i, next_j, depth + 1);
}
}
seen[i][j] = false;
};
C++ プログラム例（ABC378D）
再帰関数 dfs は、ラムダ式で記述しました（23ー39行目）。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w, k;
cin >> h >> w >> k;
vector<string> s(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
int result = 0;
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (s[i][j] == '#') {
continue;
}
vector<vector<bool>> seen(h, vector<bool>(w, false));
auto dfs = [&](auto self, int i, int j, int depth) -> void {
if (depth == k) {
++result;
return;
}
seen[i][j] = true;
for (int d = 0; d < 4; ++d) {
int next_i = i + di[d];
int next_j = j + dj[d];
if ((0 <= next_i) && (next_i < h) && (0 <= next_j) &&
(next_j < w) && !seen[next_i][next_j] &&
(s[next_i][next_j] == '.')) {
self(self, next_i, next_j, depth + 1);
}
}
seen[i][j] = false;
};
dfs(dfs, i, j, 0);
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC378D）
基本的な考え方は同じです。
「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。以下がプログラムです。
"""AtCoder Beginner Contest 378 D"""
h, w, k = map(int, input().split())
s = [input() for i in range(h)]
def dfs(i, j, depth):
global h, w, k, s, result, di, dj, seen
if depth == k:
result += 1
return
seen[i][j] = True
for d in range(4):
next_i = i + di[d]
next_j = j + dj[d]
if 0 <= next_i < h and 0 <= next_j < w and \
not seen[next_i][next_j] and s[next_i][next_j] == '.':
dfs(next_i, next_j, depth + 1)
seen[i][j] = False
result = 0
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
for i in range(h):
for j in range(w):
if s[i][j] == '#':
continue
seen = [[False for _ in range(w)] for _ in range(h)]
dfs(i, j, 0)
print(result)
最後に
当初、BFSで書いて、あるグリッドからの最短距離が $K$ となるグリッドの個数を求めていました。入力例1と2では同じ解を得ますが入力例3で間違いが分かります。
BFSを試した後、DFSを使うことが適切だと分かり、勉強になりました。
引き続き ABC の問題を紹介していきます。
