题解 | 岛屿数量

class Solution {
public:
    //深度优先遍历与i，j相邻的所有1
    void dfs(vector<vector<char>>& grid, int i, int j) { 
        int n = grid.size();
        int m = grid[0].size();
        //置为0
        grid[i][j] = '0'; 
        //后续四个方向遍历
        if(i - 1 >= 0 && grid[i - 1][j] == '1') 
            dfs(grid, i - 1, j);
        if(i + 1 < n && grid[i + 1][j] == '1') 
            dfs(grid, i + 1,j);
        if(j - 1 >= 0 && grid[i][j - 1] == '1') 
            dfs(grid, i, j - 1);
        if(j + 1 < m && grid[i][j + 1] == '1') 
            dfs(grid, i, j + 1);
    }
    int solve(vector<vector<char> >& grid) {
        int n = grid.size();
        //空矩阵的情况
        if (n == 0)  
            return 0;
        int m = grid[0].size();
        //记录岛屿数
        int count = 0; 
        //遍历矩阵
        for(int i = 0; i < n; i++){ 
            for(int j = 0; j < m; j++){
                //遍历到1的情况
                if(grid[i][j] == '1'){ 
                    //计数
                    count++; 
                    //将与这个1相邻的所有1置为0
                    dfs(grid, i, j); 
                }
            }
        }
        return count;
    }
};

//bfs解法
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        
        int count = 0;
        int m = grid.size();
        int n = grid[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    bfs(grid, i, j, m, n);
                }
            }
        }
        
        return count;
    }
    
private:
    void bfs(vector<vector<char>>& grid, int i, int j, int m, int n) {
        queue<pair<int, int>> q;
        q.push({i, j});
        grid[i][j] = '0'; // 标记为已访问
        
        // 四个方向：上、下、左、右
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            
            for (auto [dx, dy] : directions) {
                int nx = x + dx;
                int ny = y + dy;
                
                // 检查边界和是否为陆地
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1') {
                    grid[nx][ny] = '0'; // 标记为已访问
                    q.push({nx, ny});
                }
            }
        }
    }
};
//四个方位的检查也可以使用方向数组实现