AtCoder が提供しているABC（AtCoder Beginner Contest）311 のD問題をC++とPythonで解いてみました。ABC311は、2023年7月22日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Grid Ice Floor（Difficulty : 885）
問題はリンク先をご覧ください。
グリッドを処理する問題です。DFSを使いました。AtCoder Problems による Difficulty は 885 でした。
解答案
問題から、左上の座標から問題に与えられている行動（氷の上をすべる）で、たどり着けるマスの数を調べます。与えられるグリッドは岩で囲まれているため、解きやすくなっています。
以下の方針で、グリッドの氷（’.’）を触れることができる点（’o’）に書き換えていきます。
- 与えられた点から、岩があるまで与えれた方向に進む。進みながらグリッドの文字を ‘o’ に書き換える。
- 岩で止まった点から、以下の条件を満たす場合に上下左右に向かって進める。
- その方向に進むと書き換えていない ‘.’ がある。
書き換えていない氷があることを確認しない場合、入力例2の右上にある ‘C’ の文字の中に入ると（実際に入ります）、C の中をぐるぐると調べ続けます。このため、書き換える氷がないことを確認する必要があります。
また、一度とまった点は二度と調べないという方法も考えられます。
###########
.###...####
.#..#...###
.#...#...##
.#........#
.#...#....#
.#..#.....#
.###......#
..........#C++ プログラム例（ABC311D）
今回は、 私が慣れている DFS（深さ優先探索：Depth-First-Search）を使いました。上の方針に従い実装します。プログラムでの留意点は以下です。
- 右下左上の移動を配列に格納しておく（6、7行目）。
- 再帰関数 dfs の処理
- 与えられた点を ‘o’ に書き換える（11行目）。
- 与えられた方向に岩があるまで書き換えながら進む（12ー16行目）。
- その地点から、4方向について、まだ氷が残っているか調べる（19ー29行目）。
- もし、氷が残っていれば、dfs を再帰的に呼び出す（30－32行目）。
- dfs(1, 1, 右) と dfs(1, 1, 下) を呼び出す。
- グリッドの ‘o’ の個数をカウントして出力する。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
vector<string> s;
int diff_x[4] = {1, 0, -1, 0};
int diff_y[4] = {0, 1, 0, -1};
void dfs(int x, int y, int d)
{
s[y][x] = 'o';
while (s[y + diff_y[d]][x + diff_x[d]] != '#') {
s[y + diff_y[d]][x + diff_x[d]] = 'o';
x += diff_x[d];
y += diff_y[d];
}
for (int i = 0; i < 4; ++i) {
bool this_dir = false;
int this_x = x;
int this_y = y;
while (s[this_y + diff_y[i]][this_x + diff_x[i]] != '#') {
if (s[this_y + diff_y[i]][this_x + diff_x[i]] == '.') {
this_dir = true;
break;
}
this_x += diff_x[i];
this_y += diff_y[i];
}
if (this_dir) {
dfs(x + diff_x[i], y + diff_y[i], i);
}
}
}
int main()
{
int n, m;
cin >> n >> m;
s.resize(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
dfs(1, 1, 0);
dfs(1, 1, 1);
int result = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (s[i][j] == 'o') {
++result;
}
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC311D）
Python では、文字列を書き換えることができないため、リストのリスト t に変換しました（36ー42行目）。t の値は、0:氷、1:岩、2:触れることができる点 となります。
再帰関数の呼出回数を sys.setrecursionlimit で増やしています。また Python の慣用に従い、定数としか使わない変数名を大文字にしました（DIFF_X/DIFF_Y）。
"""AtCoder Beginner Contest 311 D"""
import sys
LIMIT = 10**6
sys.setrecursionlimit(LIMIT + 1)
DIFF_X = [1, 0, -1, 0]
DIFF_Y = [0, 1, 0, -1]
def dfs(x, y, d):
global t
t[y][x] = 2
while t[y + DIFF_Y[d]][x + DIFF_X[d]] != 1:
t[y + DIFF_Y[d]][x + DIFF_X[d]] = 2
x += DIFF_X[d]
y += DIFF_Y[d]
for i in range(4):
this_dir = False
this_x = x
this_y = y
while t[this_y + DIFF_Y[i]][this_x + DIFF_X[i]] != 1:
if t[this_y + DIFF_Y[i]][this_x + DIFF_X[i]] == 0:
this_dir = True
break
this_x += DIFF_X[i]
this_y += DIFF_Y[i]
if this_dir:
dfs(x + DIFF_X[i], y + DIFF_Y[i], i)
n, m = map(int, input().split())
s = [input() for i in range(n)]
t = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
for j in range(m):
if s[i][j] == '#':
t[i][j] = 1
else:
t[i][j] = 0
dfs(1, 1, 0)
dfs(1, 1, 1)
result = 0
for i in range(n):
for j in range(m):
if t[i][j] == 2:
result += 1
print(result)こちらも「AC」と判定されました。
最後に
この問題は楽しく解くことができました。ただし、途中でプログラムを間違えてデバッグに手間取り、AC が取れたのは、95分1秒でした。
D問題は解けるようになってきたので、早く解くことが必要になってきたのかもしれません。
引き続き ABC の問題を紹介していきます。
