题解 | 岛屿数量

#include <vector>
using namespace std;

class Solution {
public:
    // 方向数组：上下左右
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) {
        if (grid.empty() || grid[0].empty()) {
            return 0;
        }
        
        int rows = grid.size();
        int cols = grid[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        int islandCount = 0;
        
        // 遍历整个网格
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                // 找到未访问的陆地，开始DFS
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid, visited, i, j);
                    islandCount++;
                }
            }
        }
        
        return islandCount;
    }
    
    // DFS：标记所有相连的陆地为已访问
    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        // 标记当前位置为已访问
        visited[x][y] = true;
        
        // 探索四个方向
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 检查边界和是否为未访问的陆地
            if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size()) {
                if (grid[nx][ny] == '1' && !visited[nx][ny]) {
                    dfs(grid, visited, nx, ny);
                }
            }
        }
    }
};