题目

题解

1. DFS

  • 时间复杂度$O(MN)$
  • 空间复杂度$O(1)$
class Solution {
public:
    int dfs(vector<vector<int>>& grid, int row, int column){
        int rows = grid.size();
        int columns = grid[0].size();//计算行列数

        if(row < 0|| row > rows-1 || column < 0 || column > columns-1) return 0;
        if(grid[row][column] == 1) return 1;
        grid[row][column] = 1;//dfs过的位置归1

        int vr[] = {0,1,0,-1};
        int vc[] = {1,0,-1,0};//定义两个数组包含四个方向，用于下面DFS
        int res = 1;//先假定这是一个岛屿
        for(int i=0; i<4; i++){
            res = min(res, dfs(grid, row+vr[i], column+vc[i]));
            //res取res和dfs得到的值中小的，即四个方向有一个遍历到边界就返回0
        }
        return res;
    }
    int closedIsland(vector<vector<int>>& grid) {
        if(grid.empty()) return 0;
        int rows = grid.size();
        int columns = grid[0].size();//计算行列数
        int res = 0;

        //遍历所有的位置，计算岛屿个数
        for(int i=0; i<rows; i++){
            for(int j=0; j<columns; j++){
                if(grid[i][j] == 0){
                    res += dfs(grid, i, j);
                }
            }
        }
        return res;
    }
};

2. BFS

  • 时间复杂度$O(MN)$
  • 空间复杂度$O(min{N,M})$
class Solution {
public:
    int BFS(vector<vector<int>>& grid, int r, int c){
        int val = 1;//先定义该处属于一个岛
        int vr[] = {0,1,0,-1};
        int vc[] = {1,0,-1,0};//定义数组保存四个方向
        queue<pair<int,int>> q;//定义队列保存坐标值
        q.push(make_pair(r,c));//先把种子坐标放入队列
        while(!q.empty()){//若q不为空，继续迭代
            auto cur = q.front(); q.pop();//取队首的值
            int i = cur.first, j = cur.second;//取两个坐标
            //周围的值若没越界，且值为1
            if(i < 0 || i > grid.size()-1 || j < 0 || j > grid[0].size()-1) val = 0;//若遍历到边界，将val置0，说明该岛与边缘接触
            if(i >= 0 && i <= grid.size()-1 && j >= 0 && j <= grid[0].size()-1 && grid[i][j] == 0){
                grid[i][j] = 1;//将其变为0
                //将其四个方向的值压入队尾
                for(int k=0; k<4; ++k){
                    int x = i+vr[k];
                    int y = j+vc[k];
                    q.push(make_pair(x, y));
                }
            }
        }
        return val;
    }
    int closedIsland(vector<vector<int>>& grid) {
        if(grid.empty()) return 0;//特殊情况
        int rows = grid.size(),columns = grid[0].size();
        int res = 0;//定义存结果的res
        for(int i=0; i<rows; i++){
            for(int j=0; j<columns; j++){//遍历每个位置
                if(grid[i][j] == 0){//若该处为1，则作为种子进行bfs
                    int val = BFS(grid, i, j);
                    res += val;//BFS介绍，岛屿数+1
                }
            }
        }
        return res;
    }
};

reference

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