求助,用的bfs,TLE和MLE理解,为什么会报WA那,求解
查看原帖
求助,用的bfs,TLE和MLE理解,为什么会报WA那,求解
1087205
Luochen567楼主2023/11/5 11:05
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
int n, m,ans=0;
int zw_x[8] = {-1,-1,-1,0,1,1,1,0};
int zw_y[8] = {-1,0,1,1,1,0,-1,-1};
char a[105][105] = { 0 };
struct pos
{
	int x;
	int y;
};
queue<pos> q;
bool ssk(int x, int y)
{
	for (int i = 0; i < 8; i++)
	{
		if (a[x + zw_x[i]][y + zw_y[i]] == 'W')
		{
			return true;
		}
	}
	return false;
}
void bfs()
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (a[i][j] == '.')
			{
				continue;
			}
			if (ssk(i, j))
			{
				ans++;
				pos ls;
				ls.x = i;
				ls.y = j;
				q.push(ls);
				while (!q.empty())
				{
					pos ls2 = q.front();
					q.pop();
					a[ls2.x][ls2.y] = '.';
					for (int i = 0; i < 8; i++)
					{
						if (a[ls2.x + zw_x[i]][ls2.y + zw_y[i]] == 'W')
						{
							pos ls3;
							ls3.x = ls2.x + zw_x[i];
							ls3.y = ls2.y + zw_y[i];
							q.push(ls3);
						}
					}
				}

			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
		}
	}
	bfs();
	cout << ans;
	return 0;
}
2023/11/5 11:05
加载中...