题解 | 没挡住洪水

遍历地图，寻找‘#’，即空地单元格。

用bfs遍历该空地区域，在遍历四个方向的同时判断该空地单元格是否与水相邻，若只要该区域有一个单元格与水不相邻，则该块空地区域不会被完全淹没。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
//四个方向
vector<vector<int>> direction = { {1,0},{0,1},{-1,0},{0,-1} };

int bfs(vector<vector<char>>& map, pair<int,int> point)
{
	int rows = map.size();
	int cols = map[0].size();

	queue<pair<int, int>> q;
	q.push(point);

	int xn = 0, yn = 0;
	bool all_beside_water = true;//是否全与水相邻，即是否被完全淹没

	while (!q.empty())
	{
		bool beside_water = false;
		auto [x, y] = q.front();
		map[x][y] = '*';//已访问过用*标记
		q.pop();

		for (auto dir : direction)
		{
			xn = x + dir[0];
			yn = y + dir[1];
			if (map[xn][yn] == '.'||xn < 0 || xn >= rows || yn < 0 || yn > cols)//与水相邻
			{
				beside_water = true;
			}
			if (xn >= 0 && xn < rows && yn >= 0 && yn < cols&&map[xn][yn] == '#')//相邻空地加入队列
			{
				q.push({ xn,yn });
			}
		}
		if (beside_water == false)//只要有一个与水不相邻，即不完全与水相邻
			all_beside_water = false;
	}
	if (all_beside_water == false)//不完全与水相邻，不会被水淹没
		return 0;
	else
		return 1;
}

int main()
{
	int n;
	cin >> n;
	vector<vector<char>> map(n, vector<char>(n));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
		}
	}

	int count = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (map[i][j] == '#')//寻找空地，bfs遍历
				count += bfs(map, { i,j });
		}
	}
	cout << count;
}