题解 | 数水坑

这道题实际上还是前一道题为核心，也就是利用BFS。

本题思路是利用双重for循环遍历整个n*m田地，找到未被遍历过的水格子，作为走迷宫的“起点”。因为这是靠外循环找到的未被遍历的水格子，所以肯定是形成新水坑，那么水坑数量+1。

然后把起点塞入队列，弹出队首元素，检查它八连通区域有没有其他未被遍历的水格子，有的话就把它也标记为遍历过，同时也塞入队列，在以后弹出队列元素时就会把这些水格子也弹出来，然后就又能找出它的八连通区域的所有水格子，

最后当队列为空时，所有这些水格子就都属于一个水坑啦。

依靠着外循环遍历整个田地，我们很快就能找到所有水坑数，代码如下：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    vector<vector<int>> visited(n, vector<int>(m, 0)); // 标记当前元素是否被遍历过
    int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
    int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
    queue<pair<int, int>> a; // 队列，记录所有是w的格子
    int cnt = 0; // 记录水坑数量
    for(int i = 0; i < n; i++){ // 两个循环记录每个格子是否遍历
        for(int j = 0; j < m; j++){
            if(s[i][j] == 'W' && visited[i][j] == 0){
                cnt++; // 新的水坑
                a.push({i, j}); // 压入队列
                while(!a.empty()){ // 只要队列非空，我就一直循环找新水格子
                    pair<int, int> curr = a.front();
                    a.pop();
                    int x = curr.first;
                    int y = curr.second;
                    for(int z = 0; z < 8; z++){
                        int mx = x + dx[z];
                        int my = y + dy[z];
                        if(!(mx < 0 || my < 0 || mx >= n || my >= m)){ // 没出界
                            if(s[mx][my] == 'W' && visited[mx][my] == 0){
                                // 没被遍历过且为水格子
                                a.push({mx, my}); // 压入新的水格子
                                visited[mx][my] = 1;
                            }
                        }
                    }
                }                
                visited[i][j] = 1; // 每次遍历到它必定标记为1
            }
        }
    }
    cout << cnt;
    return 0;    
}