AtCoder が提供しているABC（AtCoder Beginner Contest）351 のD問題をC++とPythonで解いてみました。ABC351は、2024年4月27日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Grid and Magnet（Difficulty : 974）
問題はリンク先をご覧ください。
到達すると動けなくなるマスがありますが、連結成分を求める問題です。AtCoder Problems による Difficulty は 974 でした。
解答案
すべてのマスについて、連結しているマスの個数をカウントします。注意は以下です。
- 磁石が置かれているマスの隣ではないマスは、いずれかの連結成分に所属します。お互いに行き来できるマスは同じ連結成分と見なされるためです。
- 一方、磁石が置かれているマスの隣のマスは、複数の連結成分に所属する場合があります。これは、このマスを連結成分として共有していても、行き来できないマスがありえるためです。
C++ プログラム例（ABC351D）
連結成分の個数は、DFS で求めることが多いですが、今回は BFS（キュー）を使用しました。磁石の隣のマスは、’o’ に書き換えておきます（15ー29行目）。
本体部分のコード（31ー76行目）は、少し長くなりました。補足します。
- すべてのマスについて、連結成分の個数を調べます。どの連結成分に属するかは、配列 area で管理します。
- 磁石の隣のマスが始点の場合、連結成分のマスの個数として1を格納します（40ー43行目）。
- なにも置かれていないマスは、どの連結成分でもない場合に調べます（44行目のif文）。
- BFS で同じ連結成分に属するマスをキューに格納していきます。ただし、磁石の隣のマスの場合は、そこから動けないため、これ以上キューに格納しません（57ー59行目）。
- 52ー73行目は、BFSの定番コードをベースにしています。
- 連結成分のマスの個数は、配列 result に格納します（74行目）。
最後に配列 result に格納されている要素の最大値を出力して終了します。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w;
cin >> h >> w;
vector<string> s(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
}
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] == '#') {
for (int d = 0; d < 4; ++d) {
int ti = i + di[d];
int tj = j + dj[d];
if ((0 <= ti)&&(ti < h)
&&(0 <= tj)&&(tj < w)
&&(s[ti][tj] == '.')) {
s[ti][tj] = 'o';
}
}
}
}
}
vector<int> result;
queue<pair<int, int>> que;
vector<vector<int>> area(h, vector<int>(w, -1));
int area_no = 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (s[i][j] == '#') {
continue;
}
if (s[i][j] == 'o') {
result.push_back(1);
continue;
}
if ((s[i][j] == '.')&&(area[i][j] != -1)) {
continue;
}
++area_no;
int this_area = 0;
que.push(make_pair(i, j));
area[i][j] = area_no;
++this_area;
while (!que.empty()) {
pair<int, int> now = que.front();
que.pop();
int now_i = now.first;
int now_j = now.second;
if (s[now_i][now_j] == 'o') {
continue;
}
for (int d = 0; d < 4; ++d) {
int next_i = now_i + di[d];
int next_j = now_j + dj[d];
if ((0 <= next_i)&&(next_i < h)
&&(0 <= next_j)&&(next_j < w)
&&(area[next_i][next_j] != area_no)
&&(s[next_i][next_j] != '#')) {
que.push(make_pair(next_i, next_j));
area[next_i][next_j] = area_no;
++this_area;
}
}
}
result.push_back(this_area);
}
}
int max_result = 0;
for (auto e : result) {
max_result = max(max_result, e);
}
cout << max_result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC351D）
Python は文字列の変数を書き換えることができないため、mark というリストを定義して使います。基本的な考え方は、C++版と同じです。以下となります。
"""AtCoder Beginner Contest 351 D"""
from collections import deque
h, w = map(int, input().split())
s = [input() for i in range(h)]
mark = [['.' for _ in range(w)] for _ in range(h)]
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
for i in range(h):
for j in range(w):
if s[i][j] == '#':
mark[i][j] = '#'
for d in range(4):
ti = i + di[d]
tj = j + dj[d]
if 0 <= ti < h and 0 <= tj < w and mark[ti][tj] == '.':
mark[ti][tj] = 'o'
result = []
que = deque()
area = [[-1 for _ in range(w)] for _ in range(h)]
area_no = 0
for i in range(h):
for j in range(w):
if mark[i][j] == '#':
continue
if mark[i][j] == 'o':
result.append(1)
continue
if mark[i][j] == '.' and area[i][j] != -1:
continue
area_no += 1
this_area = 0
que.append((i, j))
area[i][j] = area_no
this_area += 1
while que:
now_i, now_j = que.popleft()
if mark[now_i][now_j] == 'o':
continue
for d in range(4):
next_i = now_i + di[d]
next_j = now_j + dj[d]
if 0 <= next_i < h and 0 <= next_j < w and \
area[next_i][next_j] != area_no and \
mark[next_i][next_j] != '#':
que.append((next_i, next_j))
area[next_i][next_j] = area_no
this_area += 1
result.append(this_area)
print(max(result))こちらも「AC」と判定されました。
最後に
よくあるグリッドの問題に磁石の設定を加えた問題でした。コンテスト中に解くことができて、うれしく感じました。
引き続き ABC の問題を紹介していきます。
