岛屿数量

class Solution {
public:
    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& used, int i, int j){        // 深搜
        grid[i][j]=true;
        if(i>0&&grid[i-1][j]=='1'&&used[i-1][j]==false) dfs(grid, used, i-1, j);
        if(j>0&&grid[i][j-1]=='1'&&used[i][j-1]==false) dfs(grid, used, i, j-1);
        if(i<grid.size()-1&&grid[i+1][j]=='1'&&used[i+1][j]==false) dfs(grid, used, i+1, j);
        if(j<grid[0].size()-1&&grid[i][j+1]=='1'&&used[i][j+1]==false) dfs(grid, used, i, j+1);
    }
    int numIslands(vector<vector<char>>& grid) {
        int result=0;
        vector<vector<bool>> used(grid.size(), vector<bool>(grid[0].size(), false));
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j]=='1'&&used[i][j]==false){
                    dfs(grid, used, i, j);
                    result++;
                }
            }
        }
        return result;
    }
};


class Solution {
private:
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {        // 广搜
    queue<pair<int, int>> que;
    que.push({x, y});
    visited[x][y] = true; // 只要加入队列，立刻标记
    while(!que.empty()) {
        pair<int ,int> cur = que.front(); que.pop();
        int curx = cur.first;
        int cury = cur.second;
        for (int i = 0; i < 4; i++) {
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
            if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {
                que.push({nextx, nexty});
                visited[nextx][nexty] = true; // 只要加入队列立刻标记
            }
        }
    }
}
public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    result++; // 遇到没访问过的陆地，+1
                    bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                }
            }
        }
        return result;
    }
};