个人感觉思路没什么问题,样例以及自造样例都过了
#include<bits/stdc++.h>
using namespace std;
struct node {
int x, y;
} q[25050];
const int mxn = 502;
const int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};//bfs必备方向数组
char s[mxn][mxn];//地图
int sum = 0, n, m;
void bfs(int, int);
bool is(int x, int y) {//判断点是否在地图内
return x < 1 || y < 1 || x > n || y > m;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> s[i][j];
}
}
for (int i = 1; i < n; i++) {//如果在边缘找到突破口,bfs
if (s[i][1] == '0') {
bfs(i, 1);
} else if (s[i][m] == '0') {
bfs(i, m);
}
}
for (int i = 1; i < m; i++) {
if (s[1][i] == '0') {
bfs(1, i);
} else if (s[n][i] == '0') {
bfs(n, i);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i][j] == '0') {
sum++;
}
}
}
printf("%d", sum);
return 0;
}
void bfs(int x, int y) {
int head = 0, tail = 1;
q[1].x = x;
q[1].y = y;
s[x][y] = '*';
while (head < tail) {
head++;
for (int i = 0; i < 4; i++) {
int xx = q[head].x + d[i][0];
int yy = q[head].y + d[i][1];
if (is(xx, yy)) continue;//如果点在地图外
if (s[xx][yy] == '*') continue;//如果是围墙,就不必洪水淹没
s[xx][yy] = '*';//用洪水淹没
q[++tail].x = xx;//入队
q[tail].y = yy;
}
}
}