【ABC325C】グリッドBFSで学んだことメモ
⚡ 1分で読める要約
- AtCoder ABC325 C「Sensors」で、グリッド上の連結成分を数える問題に取り組んだログです。
- 2次元配列の扱い、
charと"文字列"の違い、pair<int,int>の使い方でしっかり躓きました。 - BFS での
visited管理や範囲チェックの順番など、典型テクニックの重要さを再確認。 - 最終的には
vector<string>を使ったすっきり実装に落ち着きました。
🏁 はじめに
最近、AtCoder で水色を目指してコツコツ問題を解いています。
その中で、グリッド探索 + BFS という、いかにも競プロっぽい問題に取り組んだので、備忘録がてらまとめておきます。
今回扱ったのは AtCoder Beginner Contest 325 C 問題「Sensors」。
やってみると、実はアルゴリズム自体よりも、
- 2次元配列の宣言と初期化
charと"."の違い- 座標の軸（行・列・x・y）がこんがらがる問題
といった 実装寄りのところ でだいぶ苦戦しました。
この記事は、未来の自分がまた同じところでつまづかないようにするための、自分向けの解説メモです。
💭 問題概要
問題の内容（ざっくり）
- 縦
H行、横W列のマス目がある。 - 各マスには
.または#が書かれている。#が「センサー」。 - 上下左右・斜め（8方向）のいずれかで隣接している
#同士は「つながっている」とみなす。 - この「つながっている」センサーの塊を 1 個のセンサーと数え、全部で何個あるか を求める問題。
要は、8 方向連結な # の連結成分数を数える グリッド探索問題です。
問題リンク
🧩 実装と試行錯誤
最初はこんな感じの方針で書き始めました。
- グリッドは
vector<vector<char>>で管理 usedもvector<vector<bool>>で訪問管理- 2重ループで全マスを見る
#で未訪問のマスから BFS を始め、つながっているマスを全部たどるたびにans++
…と、方針自体は王道だったのですが、実装でかなり迷走しました。
1. 2次元配列の宣言と初期化まわり
vector<vector<char>> a(h, vector<char>(w)); vector<vector<bool>> used(h, vector<bool>(w));
ここまではよかったのですが、読み込みループの中でなぜか
used[h][w] = false;
なんて書いてしまっていて、完全に範囲外アクセス。
そもそも vector<vector<bool>> used(h, vector<bool>(w)); の時点で、全部 false 初期化されるので、ここは何も書かなくてよかったところでした。
2. char と "." の比較でコンパイルエラー
つい Python のノリで、
if (a[i][j] == "." || used[i][j]) continue;
と書いてしまい、
comparison with string literal results in unspecified behavior
ISO C++ forbids comparison between pointer and integer
のようなエラーが出て撃沈。
C++ では a[i][j] は char なので、1文字は ' '（シングルクォート） で書く必要がある、という基本を忘れていました。
if (a[i][j] == '.' || used[i][j]) continue; // こっちが正解
3. queue<pair<int,int>> の宣言ミス
queue<pair<int,int>> の宣言ミス4. 範囲チェックで軸を取り違える
BFS で隣接マスを見に行くとき、最初はこう書いていました：
if (nx >= 0 && nx < w && ny >= 0 && ny < h && !used[nx][ny]) { ... }
本来、
nxは「行」なので0 <= nx < hnyは「列」なので0 <= ny < w
でチェックすべきところを、逆にしてしまっていたパターンです。
これもバグの温床でした。
5. 始点を visited にするのを忘れる
BFS 開始時に、
queue<pair<int,int>> que; que.push({i, j});
とだけ書いていて、used[i][j] = true; をしていない状態でした。
これだと、条件によっては同じマスが何度もキューに入ったり、成分が 1 マスだけのときに used が最後まで false のままだったり、地味に危ない挙動になります。
🔍 改善の流れ
何度かコンパイルエラーや WA と戦った結果、次の点を意識して書き直しました。
1. グリッドは vector<string> にしてシンプルに
もともと
vector<vector<char>> a(h, vector<char>(w));
と書いていましたが、行ごとに 1 本の文字列で扱うほうが楽だと気づいて、
vector<string> s(h); for (int i = 0; i < h; i++) cin >> s[i];
という形に変更しました。
これで、
- 入力が 1 重ループで済む
s[r][c]でそのままcharが取れる- デバッグ時に
cout << s[i]で行をそのまま出せる
など、扱いが一気に楽になりました。
2. 座標は r, c（row, column）で考える
x, y という書き方だと、「どっちが縦だっけ？」と毎回迷ってしまったので、思い切って r, c に統一しました。
r…row（行） → 0 〜 h-1（縦）c…column（列） → 0 〜 w-1（横）
として、
int dr[8] = {1, 0, -1, 0, 1, 1, -1, -1}; int dc[8] = {0, 1, 0, -1, 1, -1, 1, -1};
と置くことで、
int nr = r + dr[d]; int nc = c + dc[d]; if (0 <= nr && nr < h && 0 <= nc && nc < w) { ... }
と書いても違和感がなくなり、軸の取り違えがかなり減りました。
3. BFS の「定石形」を身体に入れる
BFS まわりは、以下の形で「テンプレ」として覚えることにしました。
- 開始地点で
usedを true にしてからキューに突っ込む - 隣接マスも、
usedを true にしてからキューに入れる - 範囲チェック → 中身のチェック (
'#'かどうか) →usedの確認、の順で条件を書く
queue<pair<int,int>> que; used[r][c] = true; que.push({r, c}); while (!que.empty()) { auto [x, y] = que.front(); que.pop(); for (int d = 0; d < 8; d++) { int nx = x + dr[d]; int ny = y + dc[d]; if (0 <= nx && nx < h && 0 <= ny && ny < w && s[nx][ny] == '#' && !used[nx][ny]) { used[nx][ny] = true; que.push({nx, ny}); } } }
この形にしてからは、バグの入り込みどころがかなり減りました。
🚀 最終コード
最終的に AC したコードはこんな感じになりました。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int h, w; cin >> h >> w; // グリッドは行ごとに string で持つ vector<string> s(h); for (int i = 0; i < h; i++) { cin >> s[i]; } // 訪問管理用 vector<vector<bool>> used(h, vector<bool>(w, false)); // 8方向（上下左右＋斜め） int dr[8] = {1, 0, -1, 0, 1, 1, -1, -1}; int dc[8] = {0, 1, 0, -1, 1, -1, 1, -1}; int ans = 0; for (int r = 0; r < h; r++) { for (int c = 0; c < w; c++) { // センサーがない or もう訪問済みならスキップ if (s[r][c] == '.' || used[r][c]) continue; // このマスを起点に BFS して、1つの連結成分を塗りつぶす queue<pair<int,int>> que; used[r][c] = true; // キューに入れる前に visited にする que.push({r, c}); while (!que.empty()) { auto [x, y] = que.front(); que.pop(); for (int d = 0; d < 8; d++) { int nx = x + dr[d]; int ny = y + dc[d]; // 範囲チェック → '#' か → 未訪問か の順 if (0 <= nx && nx < h && 0 <= ny && ny < w && s[nx][ny] == '#' && !used[nx][ny]) { used[nx][ny] = true; que.push({nx, ny}); } } } // 1つの連結成分をまるっと探索し終えたのでカウント ans++; } } cout << ans << ' '; return 0; }
🧠 今回の学び
今回の ABC325C を通して、特に大事だなと感じたポイントは以下の通りです。
1. グリッドは「行」「列」で考える
- 配列の添字は基本的に
[行][列]。 - 座標を
r, cと書くことで、縦横の混乱がだいぶ減りました。 - 範囲チェックも「
0 <= r < H」「0 <= c < W」と書くのが自然。
「x が縦？ 横？」と毎回悩むくらいなら、最初から r/c で慣れてしまう方が精神的に楽だと思いました。
2. BFS の「型」を覚えると安心
毎回イチから考えるのではなく、以下の流れをテンプレにするとよさそうです。
- 始点のチェック
queueを用意- 始点を
visited = trueにしてキューに入れる - キューが空になるまでループ
- 取り出した頂点から隣接マスを見る
- 範囲チェック → 壁でないか → 未訪問か
- 条件を満たすマスを
visited = trueにしてキューに入れる
この「パターン」を身体に入れておくと、バグる余地が格段に減ると感じました。
3. char と "文字列" の違いは最初に叩き込む
- 1文字 →
'a'（シングルクォート） - 文字列 →
"abc"（ダブルクォート）
というルールを間違えると、コンパイルエラーが長々と出てきてつらいので、早めに慣れておくのが良さそうです。
4. 初期化はコンストラクタに任せる
vector<vector<bool>> used(h, vector<bool>(w));
と書いた時点で、自動的に全部 false で初期化されます。
ループの中で used[h][w] = false; みたいなことをしてしまうと、逆にバグの原因（範囲外アクセス）になります。
「コンストラクタで初期化できるものは素直に任せる」という感覚が大事だと感じました。
？クイズ
今回の解法の肝になっている部分を、軽いクイズ形式で振り返ります。
Q1. 次の条件分岐のうち、安全なのはどっち？
A:
if (s[nx][ny] == '#' && 0 <= nx && nx < h && 0 <= ny && ny < w) { ... }
B:
if (0 <= nx && nx < h && 0 <= ny && ny < w && s[nx][ny] == '#') { ... }
答えを見る
正解：B
if の条件は左から順に評価され、途中で false になったら以降は評価されません。
A のように最初に s[nx][ny] にアクセスしてしまうと、範囲外の添字でアクセスする可能性があり危険です。
B のように、先に範囲チェック → そのあと中身を読むのが正しい順番です。
Q2. BFS で始点をキューに入れるとき、used を true にするタイミングは？
- キューから取り出した直後に
usedを true にする - キューに入れる前に
usedを true にする
答えを見る
基本的には 2 が推奨。
- 「キューに入れる＝訪問予定」とみなして、そのタイミングで
used = trueにしておくと、同じマスを重複してキューに入れるのを防げます。 - 1 の場合でもロジックによっては正しく書けますが、ミスしやすくなるので、定石としては 2 を覚えておくのが安全です。
Q3. 8 方向移動のとき、dr / dc の組として正しいものはどれ？
int dr[4] = {1, 0, -1, 0}; int dc[4] = {0, 1, 0, -1};
int dr[8] = {1, 0, -1, 0, 1, 1, -1, -1}; int dc[8] = {0, 1, 0, -1, 1, -1, 1, -1};
答えを見る
正解：2
1 は上下左右の 4 方向だけですが、今回の問題は 斜めも含めた 8 方向連結なので、2 のように斜め成分（±1, ±1 の組）も含める必要があります。
🪜 躓いたポイント
自分用の正直メモです。
- 2次元配列の宣言が長くて嫌になりがちだったけど、
vector<string>にしてだいぶスッキリした。 a[i][j] == "."と書いてエラー祭り。1文字は' 'で書くという超基本を忘れていた。nx < w、ny < hのように縦横を逆にして、範囲チェックを間違えていた。- BFS の始点で
used[i][j] = true;を忘れて、訪問管理がふわっとしていた。 - 「x 軸 / y 軸」と考えると毎回混乱するので、今後は 最初から
r, cで統一しようと決意。
🎯 次回の目標
今回の ABC325C を通して、実装力の基礎がまだまだだな…というのを痛感しました。
今後はこんな感じで進めていきたいです。
- グリッド問題をもう何問か解いて、BFS / DFS の型をしっかり身体に染み込ませる。
- 2次元配列まわり（宣言・初期化・範囲チェック）でミスをしないように、意識して練習する。
- 実戦で書いたコードを、後から「もっと短く・読みやすく」書き直す時間をとる。
- ABC の A〜D あたりを継続的に解きつつ、基礎本（アルゴリズム系）で理論も少しずつ補強していく。
「とりあえず AC」だけで満足せず、ちゃんと振り返って言語化する習慣をつけていきたいなと思います。
