始めに
初めての投稿です。間違っている箇所があれば指摘をお願いしたいです。
問題文
お気持ち
既に探索したところを再探索しないようにBFS(幅優先探索)する。
解説
問題文より黒いマスは1つでもあれば島、そして上下左右に繋がっていればそれは繋がっている最後の部分まで1つの島と見なす、ということが分かります。
まずどのマスでもいいので黒いマスを探して、その黒いマスが含む島はどこまでの範囲かを調べる。ということを全ての黒いマスに対して行えば島の個数が求められます。
しかしながら上記のアルゴリズムを素直に実装するととんでもない時間がかかりそうですね。$N,M \leq 1000$ より $ \mathcal{O}((NM)^2)$ かかります。
そこで既に探索したマスを管理してそのマスを無視しながら、黒いマスがどこまで繋がっているかを見るようにすれば実際に探索するマスは $NM$ なので $\mathcal{O} (NM) $ になりオーダーがかなり削減されました。
実装
- 黒いマスを探す
- その黒いマスがどこまで連なっているか探索する
前提として表の入力を grid[n][m] の bool 2次元配列で受け取っています。
黒ならばtrueとしています
int w, h;
cin >> w >> h;
vector<vector<bool>> grid(h, vector<bool>(w));
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
int num;
cin >> num;
grid[i][j] = num;
}
}
まず1を実装してみます
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (!grid[i][j]) continue;
// 表の 行 i , 列 j が黒いマス！
}
}
これで黒いマスを探すことが出来ました。
次は2を実装します。
このあとこの黒いマスが縦横どこまで繋がっているかを調べるだけです。
2を実装するにあたってBFS(幅優先探索)を行います。
コードを見たほうが理解に繋がりやすいと思うので先にコードを貼ります。
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (!grid[i][j]) continue;
// 表の 行 i , 列 j が黒いマス！
queue<pair<int, int>> que;
que.emplace(i, j);
while (!que.empty()) {
auto [ci, cj] = que.front();
que.pop();
int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
for (int v = 0; v < 4; ++v) {
int ni = ci + di[v];
int nj = ci + dj[v];
if (ni < 0 || nj < 0 || ni >= h || nj >= w) continue;
if (!grid[ni][nj]) continue;
que.emplace(ni, nj);
}
}
}
}
queueに黒いマスの座標を入れて、そこから上下左右のマスが黒いマスかどうか判定しています。
auto [ci, cj] = que.front(); によってqueueに格納された基準となる黒いマスの位置を取り出しています。
この基準のマスから上下左右に見ていきます。
ni には次に見る行の座標を、njには次に見る列の座標を入れています。
di と dj には今いる位置から右、上、左、下と見ていく際の座標の移動量を入れています。
di と dj の配列を用意しておくことによって基準のマスから上下左右のマスの座標の計算が楽になります。
その次の行は配列外参照しないための記述です。
次に見るマスが白だったらそのマスはもう無視する、黒だったらそのマスをまた基準にして上下左右見ていく…という風に動いていきます。
けれどこのまま動かしてもうまく動きません。なぜならば既に見たことがあるマスも探索してしまっているからです。
3 3
0 1 1
0 0 0
0 0 0
という入力が与えられた際、右上の1 1でずっと探索し続けてしまいます。
そこで最初の解説に記述した内容を思い出します。
そこで既に探索したマスを管理してそのマスを無視しながら
既に見たことがあるマスを管理する変数を作成しましょう。
座標をそのまま添字にしたいので
vector<vector<bool>> seen(h,vector<bool>(w));
とかがいいでしょうか。
これらの考え方を全て使った実際に提出したコードが以下になります
提出コード
#include <iostream>
#include <queue>
using namespace std;
const int di[] = {0, -1, 0, 1};
const int dj[] = {1, 0, -1, 0};
int main() {
// 入力受取
int w, h;
cin >> w >> h;
vector<vector<bool>> grid(h, vector<bool>(w));
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
int num;
cin >> num;
grid[i][j] = num;
}
}
// 既に探索したかを管理する配列
vector<vector<bool>> seen(h, vector<bool>(w));
int ans = 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (seen[i][j]) continue;
if (!grid[i][j]) continue;
ans++;
queue<pair<int, int>> q;
q.emplace(i, j);
seen[i][j] = true;
while (!q.empty()) {
auto [ci, cj] = q.front();
q.pop();
for (int v = 0; v < 4; ++v) {
int ni = ci + di[v];
int nj = cj + dj[v];
// 配列外参照
if (ni < 0 || nj < 0 || ni >= h || nj >= w) continue;
// 既に見たマスなら無視
if (seen[ni][nj]) continue;
// 見ているマスが白なら無視
if (!grid[ni][nj]) continue;
seen[ni][nj] = true;
q.emplace(ni, nj);
}
}
}
}
cout << ans << endl;
}