1905. Count Sub Islands

You are given two m x n binary matrices grid1 and grid2 containing only 0's (representing water) and 1's (representing land). An island is a group of 1's connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.

An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.

Return the number of islands in grid2 that are considered sub-islands.

 

Example 1:

1905. Count Sub Islands

Input: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
Output: 3
Explanation: In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.

Example 2:

1905. Count Sub Islands

Input: grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
Output: 2 
Explanation: In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are two sub-islands.

class Solution {
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int res = 0;
        for(int i = 0; i < grid1.length; i++) {
            for(int j = 0; j < grid1[0].length; j++) {
                if(grid2[i][j] == 1) {
                    if(help(grid1, grid2, i, j)) res++;
                }
            }
        }
        return res;
    }
    
    public boolean help(int[][] grid1, int[][] grid2, int i, int j) {
        if(i < 0 || i >= grid1.length || j < 0 || j >= grid1[0].length ) return true;
        if(grid2[i][j] == 0) return true;
        if(grid1[i][j] != grid2[i][j]) return false;
        
        grid2[i][j] = 0;
        boolean flag = true;
        if(!help(grid1, grid2, i + 1, j)) flag = false;
        if(!help(grid1, grid2, i - 1, j)) flag = false;
        if(!help(grid1, grid2, i, j + 1)) flag = false;
        if(!help(grid1, grid2, i, j - 1)) flag = false;
        return flag;
    }
}

吃一堑,长一智,老老实实四个方向一个一个来。注意边界条件返回true 还是false

上一篇:python3.8 无法卸载出现No Python 3.8 installation was detected


下一篇:双 VIOS 环境如何配置心跳网卡?