题解 | 挡住洪水

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

struct Grid {
	int x;
	int y;
};

int n, m, ans;
int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char c[1005][1005];
int vis[1005][1005];

//特别说明一下题目意思，因为确实描述很逆天，下面描述在原来的基础上做修正
//1.若某片区域四周（上下左右方向）均被围墙或地图边界包围，洪水无法渗入，该区域视为安全。——> 修正为：边界外都是洪水，与边界连通的区域都会被淹没
//2.请统计不会被洪水淹没的区域数量。 ———>修正为：统计未被淹没的区域的大小(未被淹没的'0'的数量，而不是连通块数量)

//每个点只入队列一遍
int main() {
	cin >> n >> m;
	cin.ignore();
	for (int i = 0; i < n; i++) {
		cin.getline(c[i], m + 1);
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0;  j < m; j++) {
			if (!vis[i][j] && c[i][j] != '*') {
				int cnt = 0;
				bool flag = true;
				queue<Grid> q;				 
				Grid st;
				st.x = i;
				st.y = j;
				q.push(st);
				vis[st.x][st.y] = 1;
				while (!q.empty()) {
					Grid g = q.front();
					q.pop();
					if (g.x == 0 || g.y == 0 || g.x == n - 1 || g.y == m - 1) flag = false;
					cnt++;
					for (int k = 0; k < 4; k++) {
						int x = g.x + direction[k][0];
						int y = g.y + direction[k][1];
						if (x > -1 && x < n && y > -1 && y < m && !vis[x][y] && c[x][y] != '*') {
							vis[x][y] = 1;
							Grid new_grid;
							new_grid.x = x;
							new_grid.y = y;
							q.push(new_grid); 
						} 
					}
				}
				ans += flag ? cnt : 0; 
			}
  		}
	}
	cout << ans << endl;
}