1002. Count Sub Islands

Given two grids grid1 and grid2 of the same size (1 is land, 0 is water), an island in grid2 is a 'sub-island' if every cell of that island is also land in grid1. Return the number of sub-islands in grid2. The input is JSON {grid1, grid2}.

Input: JSON {grid1, grid2}.

Output: Integer — the number of sub-islands.

Examples

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: Three of grid2's islands are contained in grid1.

Input: {"grid1":[[1]],"grid2":[[1]]}
Output: 1
Explanation: Contained single cell.

Input: {"grid1":[[0]],"grid2":[[1]]}
Output: 0
Explanation: Not contained.

Constraints

• 1<=rows,cols<=500

Asked by