Map Equivalence
Geographical maps representing land and water forms can be stored in the form of a grid where 1 represents land and 0 represents water. In such a scenario, land equivalence is possible by comparing grids of two maps and checking if they have any matching land regions.
There are two grids where each cell of the grids contains either 0 or 1. If two cells share a side then they are adjacent. Cells that contain 1 form a connected region (e.g. an island) if any cell of that region can be reached by moving by row or column through the adjacent cells that contain 1. Overlay the first grid onto the second and if a region of the first grid completely matches a region of the second grid, the regions are matched.
The task is to count the total number of such matched regions in the second grid.
Example
Given two 3 x 3 grids grid1 and grid2:
grid1 = [111, 100, 100]
grid2 = [111, 100, 101]There are 2 land regions in the second grid: {(0,0), (0,1), (0,2), (1,0), (2,0)} and {(2,2)}.
Regions in grid1 cover the first land region of grid2, but not the second land region. There is 1 matching region.
Making a slight alteration to the above example:
grid1 = [111, 101, 100]
grid2 = [111, 100, 101]这道题本质上是“二维网格中的岛屿匹配”问题：先分别在两张地图中用 DFS / BFS 找出所有由 1 组成的连通块（上下左右相连），再比较第二张图中的每个连通块是否能在第一张图中找到完全一致的位置覆盖。由于题目关注的是“形状和坐标是否完全一致”，通常做法是把每个岛屿的相对坐标或绝对坐标集合记录下来，再逐个判断是否完全相同。样例中第二张图有两个连通块，其中只有一个能被第一张图完整覆盖，所以答案是 1。
