【题解】Lake Counting

题目: [Lake Counting](《20级计科ACM程序设计》–搜索入门 - Virtual Judge (sdtbu.edu.cn))

题意:

给一个字符二维图. 每个W代表一个水池, 每个水池可以和它周围八个格子中的水池连通, 问最后最少有多少水池.

思路:

• 裸BFS, 注意一下队列中存pair, 也就是坐标.
• 遍历一下每个未标记的池子是不是可以和别的池子合并, 可以的话就把所有已经合并的池子标记一下就行了.
• 遍历每个池子的周围时可以提前用两个数组记录周围格子与当前格子的坐标差值, 写起来更方便.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<string>
#include<cstring>
#include<set>
#include<map>

using namespace std;

const int N = 110;
#define ll long long
#define PII pair<int,int>

char g[N][N];
bool st[N][N];
int n, m;

void bfs(int i,int j)
{
	queue<PII>q;
	q.push(PII(i, j));
	st[i][j] = 1;

	int a1[] = { -1,0,1 }, a2[] = { -1,0,1 };
	while (q.size())
	{
		int xx = q.front().first, yy = q.front().second;
		for (int b1 = 0; b1 < 3; ++b1)
		{
			for (int b2 = 0; b2 < 3; ++b2)
			{
				int c1 = xx + a1[b1], c2 = yy + a2[b2];
				if (g[c1][c2] == 'W' && st[c1][c2] == 0)
				{
					q.push(PII(c1, c2));
					st[c1][c2] = 1;
				}
			}
		}
		q.pop();
	}
    
    return ;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
			cin >> g[i][j];
	}

	int res = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (g[i][j] == 'W' && st[i][j] == 0)
			{
				res++;
				bfs(i, j);
			}
	
	cout << res;
	return 0;
}