题目

链接：200. 岛屿数量
难度：Medium

题解

分析

本题是图论中的问题，可以先进行一定的抽象把输入数据理解为一张图。所有的数字1对应的坐标可以看作是图中的结点，相邻的1代表两个结点相连（之间存在边），否则就没有边。这样，求岛屿的数量实质是就是在求图中最大联通分量的个数，最容易想到的办法自然就是深度优先搜索和广度优先搜索了。

实现

第一版：使用队列实现的非递归的BFS

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int ret = 0;
        
        int r = grid.size();
        int c = r == 0 ? 0 : grid[0].size();
        vector<vector<bool>> flag(r, vector<bool>(c, false));
        queue<size_t> x, y;
        size_t tmp_x, tmp_y;
        for(size_t i = 0; i < r; ++i) {
            for(size_t j = 0; j < c; ++j) {
                if(flag[i][j]) continue;
                flag[i][j] = true;
                if(grid[i][j] == '1') {
                    x.push(i);
                    y.push(j);
                    ++ret;
                    while(!x.empty()) {
                        tmp_x = x.front();
                        tmp_y = y.front();
                        x.pop();
                        y.pop();
                        if(tmp_y >= 1 && !flag[tmp_x][tmp_y - 1] && grid[tmp_x][tmp_y - 1] == '1') {
                            x.push(tmp_x);
                            y.push(tmp_y - 1);
                            flag[tmp_x][tmp_y - 1] = true;
                        }
                        if(tmp_y < c - 1 && !flag[tmp_x][tmp_y + 1] && grid[tmp_x][tmp_y + 1] == '1') {
                            x.push(tmp_x);
                            y.push(tmp_y + 1);
                            flag[tmp_x][tmp_y + 1] = true;
                        }
                        if(tmp_x >= 1 && !flag[tmp_x - 1][tmp_y] && grid[tmp_x - 1][tmp_y] == '1') {
                            x.push(tmp_x - 1);
                            y.push(tmp_y);
                            flag[tmp_x - 1][tmp_y] = true;
                        }
                        if(tmp_x < r - 1 && !flag[tmp_x + 1][tmp_y] && grid[tmp_x + 1][tmp_y] == '1') {
                            x.push(tmp_x + 1);
                            y.push(tmp_y);
                            flag[tmp_x + 1][tmp_y] = true;
                        }
                    }
                }
            }
        }
        return ret;
    }
};

顺利通过全部47个测试用例，用时12ms，超过95.43%的提交记录。但是查看提交记录，发现在我之前还存在8ms、4ms、0ms三个梯队。分别阅读了它们的代表源码发现了一个共同点：它们都没有设置专门的visited来标记访问，而是直接把已经记录过的所有连通分量中的1置0，省去了不少额外空间和判断。除此之外，它们的策略均是递归或非递归的DFS。
第二版：用栈实现的非递归的DFS（这是我目前各种尝试得到的最快版本，我甚至直接提交了0ms梯队示例代码）

struct pos {
    int x;
    int y;
    
    pos(int i, int j) {
        x = i;
        y = j;
    }
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int ret = 0;
        
        r = grid.size();
        c = r == 0 ? 0 : grid[0].size();
        
        for(int i = 0; i < r; ++i) {
            for(int j = 0; j < c; ++j) {
                if(grid[i][j] == '1') {
                    dfs(grid, i, j);
                    ++ret;
                }
            }
        }
        
        return ret;
    }
    
private:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        if(grid[i][j] != '1')   return;
        
        stack<pos> q;
        q.push(pos(i, j));
        while(!q.empty()) {
            pos tmp = q.top();
            q.pop();
            grid[tmp.x][tmp.y] = 0;
            
            if(tmp.x - 1 >= 0 && grid[tmp.x - 1][tmp.y] == '1') q.push(pos(tmp.x - 1, tmp.y));
            if(tmp.x + 1 < r && grid[tmp.x + 1][tmp.y] == '1')  q.push(pos(tmp.x + 1, tmp.y));
            if(tmp.y - 1 >= 0 && grid[tmp.x][tmp.y - 1] == '1') q.push(pos(tmp.x, tmp.y - 1));
            if(tmp.y + 1 < c && grid[tmp.x][tmp.y + 1] == '1')  q.push(pos(tmp.x, tmp.y + 1));
        }
    }
    
    int r;
    int c;
};

最终用时4ms，处于第二梯队。
第三版：0ms梯队，目前还未达到。
惯例，附上最优提交截图：