200.岛屿数量 463.岛屿的周长 695.岛屿的最大面积 1254. 统计封闭岛屿的数目

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

C++

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

    void dfs(vector<vector<char>>& grid,int r,int c){
        if( !isIn(grid,r,c)) return;
        if( grid[r][c] != '1' ) return;
        grid[r][c] = '2';
        dfs(grid,r+1,c);
        dfs(grid,r-1,c);
        dfs(grid,r,c+1);
        dfs(grid,r,c-1);
    }

    bool isIn(vector<vector<char>>& grid,int r,int c){
        if (r >= grid.size() || r<0 || c >= grid[0].size() || c<0 ) return false;
        return true;
    }
};

Python

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        cnt = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    cnt = cnt + 1 #python没有cnt++这种写法 ,也不能写成cnt+1,这种写法没有真正给cnt赋值
                    self.dfs(grid,i,j)
        return cnt

    def dfs(self,grid,r,c):
        if r not in range(0,len(grid)) or c not in range(0,len(grid[0])): return
        if grid[r][c] != "1": return
        grid[r][c] = "2"
        self.dfs(grid,r+1,c)
        self.dfs(grid,r-1,c)
        self.dfs(grid,r,c+1)
        self.dfs(grid,r,c-1)

463. 岛屿的周长

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 1：

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

示例 2：

输入：grid = [[1]]
输出：4

示例 3：

输入：grid = [[1,0]]
输出：4

提示：

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] 为 0 或 1

C++

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int cnt = 0;
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(grid[i][j]==1){
                    dfs(grid,i,j,cnt);
                    break;
                }
            }
        }
        return cnt;
    }

    void dfs(vector<vector<int>>& grid, int r, int c,int& cnt){
        if( r>=grid.size() || r<0 || c>=grid[0].size() || c<0) return;
        if(grid[r][c]!=1) return;
        grid[r][c] = 2;

        if(r< grid.size()-1){
            if(grid[r+1][c]==0) cnt++;
        }
        if (r == grid.size()-1) cnt++;

        if(r>0){
            if(grid[r-1][c]==0) cnt++;
        }
        if(r==0) cnt++;

        if(c< grid[0].size()-1){
            if(grid[r][c+1]==0 ) cnt++;
        }
        if (c==grid[0].size()-1) cnt++;

        if(c>0){
            if(grid[r][c-1]==0) cnt++;
        }
        if(c==0) cnt++;

        dfs(grid,r+1,c,cnt);
        dfs(grid,r,c+1,cnt);
        dfs(grid,r-1,c,cnt);
        dfs(grid,r,c-1,cnt);
    }
};

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] 为 0 或 1

C++

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int max = 0, s = 0, r = grid.size(), c = grid[0].size();
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                if(grid[i][j]==1){
                    s = 0; //不加这句话，每经过一次dfs，s都增加
                    dfs(grid,i,j,s);
                    max = s > max ? s : max;
                }
            }
        }
        return max;
    }

    void dfs(vector<vector<int>>& grid, int r, int c, int& s){
        if(r>=grid.size() || r<0 || c>=grid[0].size() || c<0) return;
        if(grid[r][c]!=1) return;
        grid[r][c] = 2;
        s++;
        dfs(grid,r+1,c,s);
        dfs(grid,r-1,c,s);
        dfs(grid,r,c+1,s);        
        dfs(grid,r,c-1,s);
    }
};

1254. 统计封闭岛屿的数目

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。

请返回 封闭岛屿 的数目。

示例 1：

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。

示例 2：

输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出：1

示例 3：

输入：grid = [[1,1,1,1,1,1,1],
             [1,0,0,0,0,0,1],
             [1,0,1,1,1,0,1],
             [1,0,1,0,1,0,1],
             [1,0,1,1,1,0,1],
             [1,0,0,0,0,0,1],
             [1,1,1,1,1,1,1]]
输出：2

提示：

• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <=1

C++

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int cnt = 0;
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(grid[i][j] == 0) {
                    int val = 1;
                    dfs(grid, i, j, val);
                    cnt += val;
                }
            }
        }
        return cnt;
    }
    void dfs(vector<vector<int>>& grid, int r, int c, int& val){
        if(r >= grid.size() || r < 0 || c >= grid[0].size() || c < 0) { //也就是如果搜索到边界的时候，val的值就变为0了，因为已经接触到边界了，因为这样的岛屿是不符合要求的，所以不进行统计
            val = 0;
            return;
        }
        if (grid[r][c] != 0) return;
        grid[r][c] = 1;
        dfs(grid, r + 1, c, val);
        dfs(grid, r - 1, c, val);
        dfs(grid, r, c + 1, val);
        dfs(grid, r, c - 1, val);
    }
};