题解 | 岛屿数量

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=105; // 数组大小（因为n,m≤100，开105留边界）


// 全局变量：存储地图、访问标记、八方向偏移
char g[N][N];   // g[i][j]：存储地图的字符（W/.），用'0'填充边界防止越界
bool b[N][N];   // b[i][j]：标记该格子是否被访问过（避免重复处理同一岛屿）
// 八方向偏移数组（对应：右下、右、右上、下、上、左下、左、左上）
ll dx[]={1,1,1,0,0,-1,-1,-1}; 
ll dy[]={1,0,-1,1,-1,1,0,-1};


// 算法核心：DFS（深度优先搜索）—— 标记当前W所在的整个连通岛屿
// 思想：从当前W格子出发，递归遍历所有八连通的W格子，标记为已访问
void dfs(ll i, ll j){
    b[i][j] = true; // 第一步：标记当前格子为已访问（避免重复处理）
    
    // （冗余判断：因为main中只有g[i][j]是W才会调用DFS，这里可省略）
    if(g[i][j] == '.') return; 
    
    // 遍历当前格子的8个相邻方向
    for(ll k=0; k<8; k++){
        // 计算相邻格子的坐标
        ll x = i + dx[k];
        ll y = j + dy[k];
        // 合法条件：①未被访问过 ②不是边界（g[x][y]!='0'，因为边界初始化为'0'）
        if(b[x][y] == false && g[x][y] != '0'){
            dfs(x, y); // 递归处理相邻的W格子（标记整个连通块）
        }
    }
}


int main() {
    // 步骤1：输入地图尺寸n（行）、m（列）
    ll n, m;
    cin >> n >> m;
    
    // 步骤2：初始化地图边界为'0'（避免DFS时越界访问）
    memset(g, '0', sizeof g); 
    
    // 步骤3：输入地图数据（从第1行第1列开始存储，留边界）
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=m; j++){
            cin >> g[i][j];
        }
    }
    
    // 步骤4：遍历所有格子，统计W岛屿数量
    ll res = 0; // res：记录W岛屿的总数
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=m; j++){
            // 触发条件：当前格子是W + 未被访问过（说明是新岛屿的起点）
            if(b[i][j] == false && g[i][j] == 'W'){
                res++; // 新岛屿，计数+1
                dfs(i, j); // 调用DFS标记这个岛屿的所有连通格子
            }
        }
    }
    
    // 步骤5：输出最终的W岛屿数量
    cout << res;
    return 0;
}