AtCoder

ABC308 D問題(Snuke Maze)を解く

AtCoder_ABC308_D

AtCoder が提供しているABC(AtCoder Beginner Contest)308 のD問題をC++とPythonで解いてみました。ABC308は、2023年7月1日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Snuke Maze(Difficulty : 619)

問題はリンク先をご覧ください。

ABC308 D問題 Snuke Maze

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の問題でした。昔に学んだ問題を活かすことができると嬉しくなります。

ABC308 について、引き続き問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA