1905.统计子岛屿.md

1905. 统计子岛屿

给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。

如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。

请你返回 grid2 中 子岛屿 的 数目 。

示例 1：

输入：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]]
输出：3
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。

示例 2：

输入：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]]
输出：2 
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 2 个子岛屿。

提示：

• m == grid1.length == grid2.length
• n == grid1[i].length == grid2[i].length
• 1 <= m, n <= 500
• grid1[i][j] 和 grid2[i][j] 都要么是 0 要么是 1 。

解法

首先通过并查集合并grid1中的各个集合。

对于grid2中的每个陆地点：

• 通过dfs判断grid2中每一片陆地是否能被grid1中的某一个集合包含（每个点在并查集搜索到根节点相等 && grid1中该点为陆地）
• 将到达的点置为-1来避免二次遍历

最终统计完全覆盖的个数。

func countSubIslands(_grid1 [][]int, _grid2 [][]int) int {
    grid1 = _grid1
    grid2 = _grid2
    n := len(grid1)
    u = make(Union)
    for i := range grid1 {
        for j := range grid1[i] {
            if grid1[i][j] == 1 {
                if i > 0 && grid1[i-1][j] == 1 {
                    u.Merge((i-1)*n+j, i*n+j)
                }
                if j > 0 && grid1[i][j-1] == 1 {
                    u.Merge(i*n+j-1, i*n+j)
                }
            }
        }
    }
    var res int 
    for i := range grid2 {
        for j := range grid2[i] {
            if grid2[i][j] == 1 {
                if dfs(i,j,n,u.Search(i*n+j)) && grid1[i][j] == 1{
                    res++
                }
            }
        }
    }
    return res
}

var u Union
var grid1,grid2 [][]int 

func dfs(i,j,n int, p int) bool {
    grid2[i][j] = -1
    res := (u.Search(i*n+j) == p && grid1[i][j] == 1)
    if j < len(grid2[i])-1 && grid2[i][j+1] == 1 { 
        res =  dfs(i, j+1, n, p) && res
    }
    if j > 0 && grid2[i][j-1] == 1 {
        res = dfs(i, j-1, n, p) && res
    }
    if i < n-1 && grid2[i+1][j] == 1 {
        res = dfs(i+1, j, n, p) && res
    }
    if i > 0 && grid2[i-1][j] == 1 {
        res = dfs(i-1, j, n, p) && res
    }
    return res
}

type Union map[int]int

func (u Union) Search(s int) int {
	if _,ok := u[s]; !ok {
		return s
	}
	p := u[s]
	if u[p] != p {
		u[s] = u.Search(p)
	}
	return u[s]
}

func (u Union) Merge(a,b int) {
	pA,pB := u.Search(a), u.Search(b)
	if pA == pB {
		return
	}
	u[pA] = pB
}