壁でないマスに変えるマスを全探索します。
「壁でない \(2\) マスは全て、上下左右に \(1\) マス動くことを繰り返し AtCoder 村内の壁でないマスのみを通って互いに行き来可能である」という条件の判定は、幅優先探索を用いることでできます。壁でないマスに変えたマスを始点として壁でないマスのみをたどる幅優先探索をし、終わったあと全ての壁でないマスが幅優先探索で到達したかを判定すればよいです。
幅優先探索の方法は、キューを使った実装が有名で、このページに解説があります。リンク先のページでは最短経路長を求めていますが、今回は到達したかだけ保存しておけばよいです。

解答例 (C++)

#include <string>
#include <queue>
#include <vector>
#include <utility>
#include <iostream>
#include <assert.h>

const std::pair<int, int> ds[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	
	std::vector<std::string> s(n);
	for (auto &i : s) std::cin >> i;
	
	int res = 0;
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (s[i][j] == '#') {
		s[i][j] = '.';
		
		std::queue<std::pair<int, int> > que;
		std::vector<std::vector<bool> > visited(n, std::vector<bool>(m));
		
		que.push({i, j});
		visited[i][j] = true;
		
		while (que.size()) {
			auto i = que.front();
			que.pop();
			for (auto d : ds) {
				int x = i.first + d.first;
				int y = i.second + d.second;
				if (x < 0 || x >= n || y < 0 || y >= m || s[x][y] == '#' || visited[x][y]) continue;
				visited[x][y] = true;
				que.push({x, y});
			}
		}
		bool ok = true;
		for (int k = 0; k < n; k++) for (int l = 0; l < m; l++) if (s[k][l] == '.' && !visited[k][l]) ok = false;
		if (ok) res++;
		
		s[i][j] = '#';
	}
	
	printf("%d\n", res);
	
	return 0;
}