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]This problem asks you to count how many land regions in the second grid are exactly matched by a land region in the first grid. A standard approach is to use DFS or BFS to extract every connected component of 1s in each grid, then compare the regions cell by cell or by normalized coordinates. Because adjacency is 4-directional, each island can be represented as a set of cells, and a region is matched only if all of its land cells are covered by the corresponding region in the first grid. In the sample, only one connected region in the second grid has an exact match.
