정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.
#include <iostream>
#include <vector>
using namespace std;
int w, h;
vector<vector<bool>> map;
vector<vector<bool>> visited;
constexpr int dir[8][2] {
{1, 0}, {1, 1}, {0, 1}, {-1, 1}, // ↑ ↗ → ↘
{-1, 0}, {-1, -1}, {0, -1}, {1, -1} // ↓ ↙ ← ↖
};
bool isRightRange(int y, int x) {
return (0 <= y && y < h && 0 <= x && x < w);
}
void dfs(int y, int x) {
if (visited[y][x]) return;
visited[y][x] = true;
for (int i = 0; i < 8; ++i) {
int nextY = y + dir[i][0], nextX = x + dir[i][1];
if (isRightRange(nextY, nextX) && map[nextY][nextX]) dfs(nextY, nextX);
}
}
int solve() {
int fragment = 0;
for (int y = 0; y < h; ++y)
for (int x = 0; x < w; ++x)
if (map[y][x] && !visited[y][x]) {
dfs(y, x);
fragment++;
}
return fragment;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
while(true) {
cin >> w >> h;
if (w == 0 && h == 0) break;
map = visited = vector<vector<bool>> (h, vector<bool>(w, false));
for (int y = 0; y < h; ++y)
for (int x = 0; x < w; ++x) {
int var = 0; cin >> var;
map[y][x] = (var == 1);
}
cout << solve() << '\n';
}
}