题解 | 数水坑

/*基本思路是通过外层两个遍历遍历矩阵，并设置res初值为0，对每一个外层遍历水坑，这里体现为值为0，将其置为2并使res++,同时调用DFS函数将其周围8联通的格子置为2并对8联通的格子递归执行dfs，当外层遍历结束时res值即为答案
*/
#include <iostream>
#include <vector>
using namespace std;

//深度优先搜索函数
void dfs(int i, int j, vector<vector<int>>& grid){
    int n = grid.size();
    int m = grid[0].size();
    for(int a = i - 1; a <= i + 1; a++){
        for(int b = j - 1; b <= j + 1; b++){
            if(a >= 0 && a < n && b >= 0 && b < m && !(a == i && b == j)){
                if(grid[a][b] == 0){
                    grid[a][b] = 2;
                    dfs(a, b, grid);
                }
            }
        }
    }
}

int main() {
    //输入数据
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n,vector<int>(m,0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char c;
            cin >> c;
            if(c == 'W'){
                grid[i][j] = 0;
            }
            else{
                grid[i][j] = 1;
            }
        }
    }
    int res = 0;//res存储结果

    //外层循环
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(grid[i][j] == 0){
               res++;
               grid[i][j] = 2;
               dfs(i, j, grid);
            }
        }
    }
    cout << res << endl;//输出结果
    return 0;
}
// 64 位输出请用 printf("%lld")