O1820 【基础】人造星空

#include <iostream>
#include <queue>
using namespace std;

struct stu{int x, y;};
int n, m, a[105][105], ans;
int dx[] = {0, -2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2};
int dy[] = {0, 0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0};

bool check(int x, int y)
{
	if (x < 1 || x > n)return 0;
	if (y < 1 || y > m)return 0;
	if (a[x][y] == 0)return 0;
	return 1;
}

void bfs(int sx, int sy)
{
	queue <stu> q;
	q.push(stu{sx, sy});
	while (!q.empty())
	{
		stu f = q.front();
		q.pop();
		for (int i = 1; i <= 13; i++)
		{
			int nx = f.x + dx[i];
			int ny = f.y + dy[i];
			if (check(nx, ny))
			{
				a[nx][ny] = 0;
				q.push(stu{nx, ny});
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			char c;
			cin >> c;
			a[i][j] = (c == '#');
		}
	}
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (a[i][j] == 1)
			{
				bfs(i, j);
				ans++;
			}
		}
	}
	cout << ans;
	return 0;
}