■考えたこと
蟻本のLake Counting (POJ No.2386) と同じ問題。
とりあえずdfsで連結しているセンサーをなめていき
(訪れたセンサーはtrueにしておく) 再帰終了後、カウントを足すという方針で解いた。
ACしたコードは下記。
const int di[] = { 1, 0, -1, 0, 1, 1, -1, -1 }; const int dj[] = { 0, 1, 0, -1, 1, -1, 1, -1 }; int main() { int h, w; cin >> h >> w; vector<string> s(h); for (int i = 0; i < h; i++) cin >> s[i]; vector<vector<bool>> visited(h, vector<bool>(w)); auto dfs = [&](auto dfs, int i, int j) -> void { visited[i][j] = true; for (int v = 0; v < 8; v++) { int ni = i + di[v]; int nj = j + dj[v]; if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue; if (visited[ni][nj]) continue; if (s[ni][nj] != '#') continue; dfs(dfs, ni, nj); } }; int ans = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (s[i][j] != '#') continue; if (visited[i][j]) continue; dfs(dfs, i, j); ans++; } } cout << ans << endl; }