https://leetcode-cn.com/problems/number-of-islands/

我的方法一：广度优先搜索

步骤

1. 优先从左到右，从上到下，找到第一个1（陆地）
2. 然后以该陆地开始广度优先搜索，每搜索到一个陆地，就设置标志为2（遍历过的陆地），当无法再扩展时，说明周围全是水包围，表示找到一个岛屿
3. 再开始遍历找到下一个陆地，还是按照第2步开始搜索
4. 当陆地的数量为0时，表示搜索完毕

初始条件

1. island_count = 0

边界条件

1. 陆地数量为0时，返回island_count
2. 广度搜索时，考虑到二维网格的边界

复杂度

时间复杂度：O(N)，每个点被遍历一次
空间复杂度：O(1)，不需要额外的空间

超时代码

逻辑应该对，但是会超时

struct Position{
    int x = 0;
    int y = 0;

    Position(){

    }

    Position(int x, int y){
        this->x = x;
        this->y = y;
    }
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size() == 0){
            return 0;
        }
        if(grid[0].size() == 0){
            return 0;
        }

        int height = grid.size();
        int width = grid[0].size();
        int island_count = 0;
        
        Position land;
        while(land.x >= 0 && land.y >= 0){
            //find the first land
            bool has_land = false;
            for(int i = land.y; i<grid.size(); i++){
                land.x = -1;
                land.y = -1;
                for(int j = 0; j<grid[i].size(); j++){
                    if(grid[i][j] == '1'){
                        land.x = j;
                        land.y = i;
                        has_land = true;
                        break;
                    }
                }
                if(has_land){
                    break;
                }
            }
            //no land, finish search
            if(!has_land){
                land.x = -1;
                land.y = -1;
                break;
            }

            //bfs
            queue<Position> lands_found;
            lands_found.push(land);
            while(!lands_found.empty()){
                Position p = lands_found.front();
                lands_found.pop();
                grid[p.y][p.x] = '2';//a land walked
                {
                    //check left
                    if(p.x-1 >= 0 && grid[p.y][p.x-1] == '1'){
                        lands_found.push(Position(p.x-1, p.y));
                    }
                    //check right
                    if(p.x+1 < width && grid[p.y][p.x+1] == '1'){
                        lands_found.push(Position(p.x+1, p.y));
                    }
                    //check top
                    if(p.y-1 >= 0 && grid[p.y - 1][p.x] == '1'){
                        lands_found.push(Position(p.x, p.y - 1));
                    }
                    //check bottom
                    if(p.y+1 < height && grid[p.y + 1][p.x] == '1'){
                        lands_found.push(Position(p.x, p.y + 1));
                    }
                }
            }
            island_count++;
        }

        return island_count;
    }
};