ABC325 C - Sensors

■考えたこと

蟻本の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;
}