文章

26

粉丝

0

获赞

82

访问

2.8k

头像
极大连通图个数 BFS方法的题解模板喵:
P1975 四川大学2024年机试题
发布于2026年2月14日 22:54
阅读数 105

#include<bits/stdc++.h>
using namespace std;
int dx[8] = {-1, 1, 0, 0, -1, 1, -1, 1};
int dy[8] = {0, 0, -1, 1, -1, -1, 1, 1};
const int N = 105;
char mp[N][N];
bool visited[N][N];
int h, w;
int col = 0;

bool judge(int x, int y)
{
	if(x > h || x < 1 || y > w || y < 1) return false;
	if(visited[x][y]) return false;
	if(mp[x][y] != 'w') return false;
	return true;
}
void bfs(int x, int y)
{
	queue<pair<int, int>> q;
	q.push({x, y});
	visited[x][y] = true;
	
	while(!q.empty())
	{
		auto ele = q.front(); q.pop();
		int xx = ele.first; int yy = ele.second;
		for(int i = 0; i < 8; i ++)
		{
			int nx = xx + dx[i]; int ny = yy + dy[i];
			if(judge(nx, ny))
			{
				q.push({nx, ny});
				visited[nx][ny] = true;
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> h >> w;
	memset(visited, 0, sizeof(visited));
	for(int i = 1; i <= h; i ++)
	{
		for(int j = 1; j <= w; j ++)
...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发