1097. 池塘计数 题解

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;

int n, m, cnt;
char g[N][N];
bool vis[N][N];

void bfs(int sx, int sy)
{
    queue<PII>q;
    q.push({sx, sy});                                                                                                                                   
    vis[sx][sy] = true;
    
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        
        for (int i = t.x - 1; i <= t.x + 1; i++)
            for (int j = t.y - 1; j <= t.y + 1; j++)
            {
                if (i == t.x && j == t.y)   continue;  // 本身这块要跳过
                if (i < 0 || i >= n || j < 0 || j >= m) continue;
                if (g[i][j] == '.' || vis[i][j])    continue;
                
                q.push({i,j});
                vis[i][j] = true;
            }
    }
}

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