BFS算法1TLE 1MLE求调
查看原帖
BFS算法1TLE 1MLE求调
724454
CCX_Ug楼主2024/5/18 21:40
#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

int n, m;
char s[110][110];
int ans;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, 1, -1};

void bfs(int sx, int sy)
{
	queue<PII> q;
	q.push({sx, sy});
	while (!q.empty())
	{
		PII t = q.front();
		q.pop();
		int x = t.first, y = t.second;
		s[x][y] = '.';
		for (int i = 0; i < 8; i++)
		{
			int kx = x + dx[i], ky = y + dy[i];
			if (kx < 0 || kx >= n || ky < 0 || ky >= m)
				continue;
			if (s[kx][ky] == '.') continue;
			q.push({kx, ky});
		}
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%s", s[i]);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (s[i][j] == 'W')
			{
				ans++;
				bfs(i, j);
			}
	printf("%d\n", ans);
	
	return 0;
}

1716039485025.png

碰到MLE的情况一定是爆queue了,但我仔细检查了BFS函数也没有发现可以爆queue的地方。求大佬调试!

2024/5/18 21:40
加载中...