この問題はセンサを頂点として、上下左右に隣接しているセンサの間に辺を張ったときのグラフの連結成分の個数を求める問題です。
グラフの連結成分の個数は以下のようにすることで時間計算量 \(O(HW)\) で求めることができます。

• 答えを \(0\) で初期化する。
• 未訪問の頂点がある限り、以下を繰り返す。
  • 未訪問の頂点を \(1\) つ選ぶ。
  • その頂点から DFS や BFS を行うことで、その頂点と同じ連結成分にある頂点をすべて訪問する。
  • 答えに \(1\) を加算する。

実装例

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
template<class T> using P = pair<T, T>;
int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,1,-1 };

int main() {
	int h, w;
	cin >> h >> w;
	vector<vector<char>> s(h, vector<char>(w));
	for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) cin >> s[i][j];
	int ans = 0;
	vector<vector<bool>> used(h, vector<bool>(w));
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (s[i][j] == '.' or used[i][j]) continue;
			queue<P<int>> que;
			que.push({ i,j });
			while (!que.empty()) {
				P<int> p = que.front(); que.pop();
				int x = p.first, y = p.second;
				for (int d = 0; d < 8; d++) {
					int nx = x + dx[d];
					int ny = y + dy[d];
					if (0 <= nx && nx < h && 0 <= ny && ny < w && s[nx][ny] == '#' && !used[nx][ny]) {
						used[nx][ny] = true;
						que.push({ nx,ny });
					}
				}
			}
			ans++;
		}
	}
	cout << ans << endl;
}