AtCoder が提供しているABC（AtCoder Beginner Contest）308 のD問題をC++とPythonで解いてみました。ABC308は、2023年7月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Snuke Maze（Difficulty : 619）
問題はリンク先をご覧ください。
DFS を用いてグリッドを処理していきます。AtCoder Problems による Difficulty は 619 でした。
解答案
DFS を用いてグリッドを処理していきます。ABC269D問題では、DFS で連結している島の数をカウントしましたが、似たようなプログラムとなります。
今回の問題で扱っている “snuke” は、同じ文字がありません。このため一度訪れたグリッド座標を訪れる必要はありません。
関数 dfs は、引数 x、y、index を取ります。x、y は調べるグリッド座標となります。index は、グリッド座標が持つ文字の文字列 “snuke” におけるインデックスとなります。以下の処理をします。
- そのグリッド座標を訪問済とする。
- 隣接しているグリッド座標が以下の条件を満たすとき、そのグリッド座標を調べる。
- H行W列の範囲に含まれている。
- まだ訪問されていない。
- “snuke” の次の文字列になっている。
dfs(0, 0, 0) を呼び出して、座標 (h – 1, w – 1) が訪問済か調べます。
C++ プログラム例（ABC308D）
上の考察に従いプログラムします。以下は、プログラムでの工夫です。
- 隣接するか調べるために配列 diff_x と diff_y を用意する（10、11行目）。
- 最初の座標 (0, 0) は調べておく（35ー38行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
string snuke = "snuke";
int h, w;
vector<vector<bool>> seen(501, vector<bool>(501, false));
vector<string> s(501);
int diff_x[4] = {1, 0, -1, 0};
int diff_y[4] = {0, 1, 0, -1};
void dfs(int x, int y, int index)
{
seen[x][y] = true;
int next = (index + 1) % 5;
for (int i = 0; i < 4; ++i) {
if (((0 <= diff_x[i] + x)&&(diff_x[i] + x < h))
&& ((0 <= diff_y[i] + y)&&(diff_y[i] + y < w))
&& (!seen[diff_x[i] + x][diff_y[i] + y])
&& (s[diff_x[i] + x][diff_y[i] + y] == snuke[next])) {
dfs(diff_x[i] + x, diff_y[i] + y, next);
}
}
}
int main()
{
cin >> h >> w;
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
if (s[0][0] != 's') {
cout << "No" << endl;
return 0;
}
dfs(0, 0, 0);
if (seen[h - 1][w - 1]) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC308D）
Python 版も同じ考え方でプログラムします。以下は Python 特有の補足です。
- 再帰呼び出しの回数の上限を設定します（2ー5行目）。
- 座標のチェックは、chained-comparison な書き方をしました（18、19行目）。
- 文字列 “snuke” の変数名は定数扱いなので、変数名を大文字にしました（25行目）。
"""AtCoder Beginner Contest 308 D"""
import sys
LIMIT = 10**6
sys.setrecursionlimit(LIMIT + 1)
def dfs(x, y, index):
global SNUKE
global h, w
global seen
global diff_x, diff_y
seen[x][y] = True
n = (index + 1) % 5
for i in range(4):
if 0 <= diff_x[i] + x < h and \
0 <= diff_y[i] + y < w and \
not seen[diff_x[i] + x][diff_y[i] + y] and \
s[diff_x[i] + x][diff_y[i] + y] == SNUKE[n]:
dfs(diff_x[i] + x, diff_y[i] + y, n)
SNUKE = "snuke"
seen = [[False for i in range(501)] for j in range(501)]
diff_x = [1, 0, -1, 0]
diff_y = [0, 1, 0, -1]
h, w = map(int, input().split())
s = [input() for i in range(h)]
if s[0][0] != 's':
print("No")
sys.exit(0)
dfs(0, 0, 0)
print("Yes" if seen[h - 1][w - 1] else "No")こちらも「AC」と判定されました。
最後に
ABC269D問題は、このブログで最初に紹介したABCの問題でした。昔に学んだ問題を活かすことができると嬉しくなります。
引き続き ABC の問題を紹介していきます。
