全WA求调
查看原帖
全WA求调
1004026
__Charlie_Chen__楼主2023/11/29 21:09

个人感觉思路没什么问题,样例以及自造样例都过了

#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;
		}
	}
}
2023/11/29 21:09
加载中...