染色问题，这里使用的方法修改了传入的参数grid，这个题目也可以使用并查集方法解决。

class Solution {
private:
    int m;
    int n;
void dfs(vector<vector<char>>& grid,int i,int j) {
    
    if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] != '1')
        return;

    grid[i][j] = '0';

    dfs(grid,i-1,j);
    dfs(grid,i+1,j);
    dfs(grid,i,j-1);
    dfs(grid,i,j+1);     
}

public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        if(m <= 0) return 0;
        n = grid[0].size();
        
        int count = 0;
        for(int i = 0;i < m;i++)
        {
            for(int j = 0;j < n;j++)
            {
                if(grid[i][j] == '1')
                {
                    dfs(grid,i,j);
                    count++;
                }
            }
        }
        
        return count;
    }
    
};

运行结果:

Runtime: 12 ms, faster than 99.94% of C++ online submissions for Number of Islands.
Memory Usage: 9.4 MB, less than 99.81% of C++ online submissions for Number of Islands.

使用DFS相对比较好理解，如果使用BFS的话代码应该如何实现呢?

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if(m <= 0) return 0;
        int n = grid[0].size(),cnt = 0;
        int offset[]={0,1,0,-1,0};
        for(int i = 0;i < m;i++)
        {
            for(int j = 0;j < n;j++)
            {
                if(grid[i][j] == '1')
                {
                    cnt += 1;
                    queue<pair<int,int>> q;
                    grid[i][j] = 0;
                    q.push({i,j});
                    while(!q.empty())
                    {
                        pair<int,int> p = q.front();
                        q.pop();
                      
                        for(int k = 0;k < 4;k++)
                        {
                            int r = p.first + offset[k];
                            int c = p.second + offset[k+1];
                             
                            if(r < m && c < n && r>=0 && c >=0 && grid[r][c]=='1')
                            {
                                 
                                grid[r][c] = '0';
                                q.push({r,c});
                                 
                            }
                            
                        }
                       
                    }
                }
            }
        }
        
        return cnt;
    }
};

运行效率

Runtime: 16 ms, faster than 80.63% of C++ online submissions for Number of Islands.
Memory Usage: 10.2 MB, less than 29.44% of C++ online submissions for Number of Islands.

BFS中需要使用queue结构，这里有个值得注意的技巧是offset {0,1,0,-1,0}
遍历网格时使用offset可以达到访问上下左右元素的目的，如果只能向上或者向下，可以修改offset来完成。