This is the sixth day of my participation in Gwen Challenge

5791. Statistical sub-islands

You are given two m x n binary matrices, GRId1 and grid2, which contain only 0 (for water) and 1 (for land). An island is a region of adjacent 1s in four directions (horizontal or vertical). Any area outside the matrix is considered water.

If an island of Grid2 is fully contained by an island of Grid1, that is, every cell of that island in GriD2 is fully contained by the same island in Grid1, then the island in grid2 is called a sub-island.

Please return the number of neutron islands in grid2.

Example:

Input: ,1,1,0,0 grid1 = [[1], [0,1,1,1,1], [0,0,0,0,0],,0,0,0,0 [1], [1,1,0,1,1]]. ,1,1,0,0 grid2 = [[1], [0,0,1,1,1], [0,1,0,0,0],,0,1,1,0 [1], [0,1,0,1,0]] output: 3: as shown in the above, the left side for grid1, for grid2 on the right. Area 1 marked in red on GRID2 is a sub-island, with a total of 3 sub-islands.Copy the code

Input: ,0,1,0,1 grid1 = [[1],,1,1,1,1 [1], [0,0,0,0,0],,1,1,1,1 [1], [1,0,1,0,1]]. ,0,0,0,0 grid2 = [[0],,1,1,1,1 [1], [0,1,0,1,0], [0,1,0,1,0], [1,0,0,0,1]] output: 2: as shown in the above, the left side for grid1, for grid2 on the right. The region 1 marked in red on GRID2 is a subisland, with a total of 2 subislands.Copy the code

prompt

  • m == grid1.length == grid2.length
  • n == grid1[i].length == grid2[i].length
  • 1 <= m, n <= 500
  • Grid1 [I][j] and grid2[I][j] are either 0 or 1.

Analysis of personal Ideas

Method 1: DFS

  1. traversegrid2Find the location of each island
  2. Scope of DFS channel sub-islands
  3. withgrid1Compare to see if you are completely surrounded
class Solution {
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int ans = 0;
        for(int i = 0; i < grid2.length; ++i){
            for(int j = 0; j < grid2[0].length; ++j){
                // Find each island in Grid2 and determine if it is surrounded by GriD1
                if(grid2[i][j] == 1&& dfs(grid1, grid2, i, j)){ ++ans; }}}return ans;
    }

    public boolean dfs(int[][] grid1, int[][] grid2, int m, int n){
        // boundary judgment
        if(m < 0 || m >= grid2.length || n < 0 || n >= grid2[0].length || grid2[m][n] == 0) {return true;
        }

        // If it exceeds the range of grid1, return directly
        if(grid1[m][n] == 0) {return false;
        }

        // Change the traversal of islands to 0 to prevent overflow
        grid2[m][n] = 0;

        // Go up, down, left, and right to search for the island
        If an island is not included, it is not a child island
        boolean flag = true;
        flag &= dfs(grid1, grid2, m + 1, n);
        flag &= dfs(grid1, grid2, m - 1, n);
        flag &= dfs(grid1, grid2, m, n + 1);
        flag &= dfs(grid1, grid2, m, n - 1);
        
        // Return the result
        returnflag; }}Copy the code

Submit the results

leetcode-cn.com/problems/co…