作者的话：

感觉不如深度优先搜索（）表达能力不行，我讲的可能不太明白。

---

分析

题意

题目：有一块 $N×M$ 的土地，雨后积起了水，有水标记为‘W’，干燥为‘.’。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼。

实际上，这道题目是一道典型的“连通块”类型题目，即在全图查找四个方向或八个方向上相互连通的节点。一般来说，我们用深度优先搜索（dfs）和广度优先搜索（bfs）去做这类题。

思路

这题我采用了广度优先搜索。
我们需要循环遍历整块土地，当遇到有水的土地（即‘W’）时，往它的右、右下、下、左下、左、左上、上、右上这八个方向去继续查找有水的土地，然后一直循环直到全部都找出来。
用一般的话说，就是将第一个有水的位置压入队列，然后while循环每次取队首，去八方向循环尝试，如果还有的话就将新的位置填充为干燥的土地（即‘.’），然后把新的压入队列。每次结束查找后就将计数变量+1，最后输出计数变量。

---

代码

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

int n,m,cnt;
char map[115][115];
int dir[8][2] = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};

struct node{
    int x,y;
};

void bfs(int x,int y){
    queue<node> q;
    q.push({x,y});
    while (!q.empty()){
        node r = q.front();
        q.pop();
        for (int i = 0;i < 8;i++){
            int nx = r.x + dir[i][0];
            int ny = r.y + dir[i][1];
            if (nx >= 0 && ny >= 0 && nx <= n && ny <= m && map[nx][ny] == 'W'){
                map[nx][ny] = '.';
                q.push({nx,ny});
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for (int i = 0;i < n;i++){
        for (int j = 0;j < m;j++){
            cin >> map[i][j];
        }
    }
    for (int i = 0;i < n;i++){
        for (int j = 0;j < m;j++){
            if (map[i][j] == 'W'){
                bfs(i,j);
                cnt++;
            }
        }
    }
    cout << cnt;
    return 0;
}

---

2024年09月08日 版本1