迷路探索系のBFS・DFSの練習になると思います。
↓問題
問題概要
M×Nのグリッドが与えられます。各マスは0または1です。
1のマスのかたまりをそれぞれ「島」と呼びます。
島の数を計算して出力してください。
画像は島が4つの例。
制約
1 ≦ N,M ≦ 1,000
(テストケース10個のうち、8個は1 ≦ N,M ≦ 100）（やさしい）
解法
深さ優先探索、幅優先探索を行うと解けます。
深さ優先探索、幅優先探索を知らない人は、様々なわかりやすい記事がすでにあるので、そちらを読んでみるといいです。
色々読みましたが、結局けんちょんさんの記事が一番わかりやすいですね（当社比）。
【深さ優先探索】
【幅優先探索】
（↓ほぼ答えの記事↓）
私は、幅優先探索で解きました。どっちでもいい場合は、だいたい幅優先探索を使うようにしてます。好きなので。
迷路やグラフの最短経路問題を解くアルゴリズムとして紹介されることが多い幅優先探索ですが、今回の問題のように迷路(グラフ)の連結成分を数えるのにもよく使います。
今回の問題だと、1回の幅優先探索が1つの島と対応するので、幅優先探索が1回終わるたびに答えを1ずつ増やしていけばいいですね。ただし、なんども同じ島を探索しないように、探索したことのある場所を配列で管理しておく必要があります。
また、上記の記事にも書いてありますが、迷路探索系の問題は、上下左右のマスへの移動をうまく実装する必要があり、以下のように先に4つの方向を定義するのが主流です。
// vectorでの定義
const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};
// 短いのが好きな人はこっちでも
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
最後に計算量ですが、一般に、頂点数$N$、辺数$M$のグラフを幅優先探索するときの計算量は$O(N+M)$です。
今回は迷路なので、頂点数は$NM$個。
辺は、それぞれの頂点から多くても4本ずつしか出ていないので、多めに見積もっても$4NM$本。
$NM+4NM=5NM$なので、計算量は$O(NM)$になり、十分高速ですね。
コード（幅優先探索）
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// マス間の上下左右の移動を定義
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n,m;
// 探索したことのある場所か」を管理する配列
vector<vector<bool>> visited;
// 幅優先探索の実装
void bfs(vector<vector<int>>& G, int x0, int y0){
// 最初に訪問する地点をキューに入れる
queue<pair<int,int>> q;
q.push({x0, y0});
while(!q.empty()){
auto [x,y] = q.front();
q.pop();
// 4方向への移動を試す
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
// 新たなマスが、場外ならダメ
if (nx < 0 || nx >= n|| ny < 0 || ny >= m) continue;
// 新たなマスが、島じゃないならダメ
if (G[nx][ny] == 0) continue;
// 新たなマスが、訪問済みならダメ
if (visited[nx][ny]) continue;
// 新たなマスへ訪問する
q.push({nx, ny});
visited[nx][ny] = true;
}
}
}
int main(void){
// 入力
cin >> m >> n;
visited.assign(n, vector<bool>(m, false));
vector<vector<int>> G(n, vector<int>(m));
for(int i = 0; i < n; i++){
for(int j=0;j<m;j++){
cin >> G[i][j];
}
}
int ans = 0;
// すべての迷路のマスに対して、幅優先探索を試みる
for(int x = 0; x < n; x++){
for(int y = 0; y < m; y++){
// 島じゃないならしない
if(G[x][y] == 0) continue;
// 訪問済みならしない
if(visited[x][y]) continue;
//幅優先探索
bfs(G, x, y);
// BFSが1回終わったら、答えの島の数を1つ増やす
ans++;
}
}
cout << ans << endl;
return 0;
}
コード（深さ優先探索）
実は深さ優先探索は幅優先探索のキューをスタックにするだけでいいので、とても簡単です。
再帰を用いた実装もあり、そっちは非常に簡潔ですが、私は再帰が苦手なのでこっちのほうが好きです。
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// マス間の上下左右の移動を定義
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n,m;
// 探索したことのある場所か」を管理する配列
vector<vector<bool>> visited;
// 深さ優先探索の実装
void dfs(vector<vector<int>>& G, int x0, int y0){
// 最初に訪問する地点をスタックに入れる
stack<pair<int,int>> st;
st.push({x0, y0});
while(!st.empty()){
auto [x,y] = st.top();
st.pop();
// 4方向への移動を試す
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
// 新たなマスが、場外ならダメ
if (nx < 0 || nx >= n|| ny < 0 || ny >= m) continue;
// 新たなマスが、島じゃないならダメ
if (G[nx][ny] == 0) continue;
// 新たなマスが、訪問済みならダメ
if (visited[nx][ny]) continue;
// 新たなマスへ訪問する
st.push({nx, ny});
visited[nx][ny] = true;
}
}
}
int main(void){
// 入力
cin >> m >> n;
visited.assign(n, vector<bool>(m, false));
vector<vector<int>> G(n, vector<int>(m));
for(int i = 0; i < n; i++){
for(int j=0;j<m;j++){
cin >> G[i][j];
}
}
int ans = 0;
// すべての迷路のマスに対して、幅優先探索を試みる
for(int x = 0; x < n; x++){
for(int y = 0; y < m; y++){
// 島じゃないならしない
if(G[x][y] == 0) continue;
// 訪問済みならしない
if(visited[x][y]) continue;
// bfs(G, x, y);
//深さ優先探索
dfs(G, x, y);
// DFSが1回終わったら、答えの島の数を1つ増やす
ans++;
}
}
cout << ans << endl;
return 0;
}