题解 | 数水坑

#include <stdio.h>

#define MAXN 105

char g[MAXN][MAXN];
int v[MAXN][MAXN];
int dx[8] = {0, 0, 1, -1, 1, -1, -1, 1};
int dy[8] = {-1, 1, 0, 0, 1, -1, 1, -1};
int n, m;

struct q {
    int x, y;
} queue[MAXN * MAXN * 2];//防止队列溢出

void bfs(int a, int b) {
    int f = 0, t = 0;
    queue[t].x = a;
    queue[t].y = b;
    t++;
    v[a][b] = 1;
    
    while (f < t) {
        int x = queue[f].x;
        int y = queue[f].y;
        f++;
        
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m 
                && g[nx][ny] == 'W' && !v[nx][ny]) {
                v[nx][ny] = 1;
                queue[t].x = nx;
                queue[t].y = ny;
                t++;
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    
    // ✅ 用 %c 读取，空格会自动跳过（格式字符串中的空格）
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %c", &g[i][j]);  // 注意 %c 前面的空格！
        }
    }
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!v[i][j] && g[i][j] == 'W') {
                bfs(i, j);//调用过几次bfs（广度优先搜索）就是几个水洼
                count++;
            }
        }
    }
    printf("%d\n", count);
    return 0;
}