AtCoder が提供しているABC（AtCoder Beginner Contest）300 のC問題をC++とPythonで解いてみました。ABC300は、2023年4月29日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Cross（Difficulty : 534）
問題はリンク先をご覧ください。
与えられたグリッドの中にある特定の形を探す問題です。AtCoder Problems による Difficulty は 534 でした。
解答案
与えられたグリッドに含まれている「×」の字を探します。以下の制約があります。
- 「×」の字を構成する文字 ‘#’ は、すべて「×」に含まれています。
- それぞれの「×」の字は隣接していません。
C++ プログラム例（ABC300C）
文字 ‘#’ を見つけたら、関数 check を呼び出します。この関数は斜め4方向を調べて、「×」の字の長さを返します。関数の戻り値を配列 result に格納します。
関数 check では、一時変数 _n に対して斜め4方向を調べて、4方向に ‘#’ があるばあいに、変数 n を更新しています。配列内へのアクセスチェックをする条件は少し長くなりました。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int h, w;
vector<string> c;
int check(int i, int j)
{
int n = 0;
while (true) {
int _n = n + 1;
if (!((i + _n < h)&&(j + _n < w)&&(c[i + _n][j + _n] == '#'))) {
break;
}
if (!((i + _n < h)&&(j - _n >= 0)&&(c[i + _n][j - _n] == '#'))) {
break;
}
if (!((i - _n >= 0)&&(j + _n < w)&&(c[i - _n][j + _n] == '#'))) {
break;
}
if (!((i - _n >= 0)&&(j - _n >= 0)&&(c[i - _n][j - _n] == '#'))) {
break;
}
++n;
}
return n;
}
int main()
{
cin >> h >> w;
c.resize(h);
for (int i = 0; i < h; ++i) {
cin >> c[i];
}
int n = min(h, w);
vector<int> result(n + 1, 0);
for (int i = 1; i < h - 1; ++i) {
for (int j = 1; j < w - 1; ++j) {
if (c[i][j] == '#') {
++result[check(i, j)];
}
}
}
for (int i = 1; i <= n; ++i) {
cout << result[i] << " \n"[i == n];
}
return 0;
}2024/5/2追記
ブログ記事では、上記のプログラムを紹介しましたが、DFSで連結成分の個数を求める方が楽でした。その方針のプログラムは以下です。
#include <bits/stdc++.h>
using namespace std;
int h, w;
vector<string> c;
int dfs(int i, int j)
{
int result = 1;
c[i][j] = '.';
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
if ((0 <= di + i)&&(di + i < h)&&
(0 <= dj + j)&&(dj + j < w)&&
(c[di + i][dj + j] == '#')) {
result += dfs(di + i, dj + j);
}
}
}
return result;
}
int main()
{
cin >> h >> w;
c.resize(h);
for (int i = 0; i < h; ++i) {
cin >> c[i];
}
int n = min(h, w);
vector<int> result(n + 1, 0);
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (c[i][j] == '#') {
++result[(dfs(i, j) - 1) / 4];
}
}
}
for (int i = 1; i <= n; ++i) {
cout << result[i] << " \n"[i == n];
}
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC300C）
C++のロジックをそのまま Python に書き直しました。結果を格納するリスト result は、添え字が1以上の場合のみ出力するため、スライス表記を使っています（29行目）。
"""AtCoder Beginner Contest 300 C"""
def check(i, j):
n = 0
while True:
_n = n + 1
if not (i + _n < h and j + _n < w and c[i + _n][j + _n] == '#'):
break
if not (i + _n < h and j - _n >= 0 and c[i + _n][j - _n] == '#'):
break
if not (i - _n >= 0 and j + _n < w and c[i - _n][j + _n] == '#'):
break
if not (i - _n >= 0 and j - _n >= 0 and c[i - _n][j - _n] == '#'):
break
n += 1
return n
h, w = map(int, input().split())
c = [input() for i in range(h)]
n = min(h, w)
result = [0] * (n + 1)
for i in range(1, h - 1):
for j in range(1, w - 1):
if c[i][j] == '#':
result[check(i, j)] += 1
print(*result[1:])こちらも「AC」と判定されました。
最後に
この問題は、特定のアルゴリズムの知識が無くても解くことができます。その一方、配列の範囲内チェックが必要であったり、条件も多いため、プログラミングに注意が必要な問題でした。
引き続き ABC の問題を紹介していきます。
