You are given a non-empty grid containing only 0 and 1.
Each 1 represents land, and each 0 represents water.
An island is a connected group of land cells. Two land cells are connected if they share a side horizontally or vertically.
You may assume that all four outer edges of the grid are surrounded by water.
Your task is to count how many distinct island shapes exist in the grid.
Two islands are considered the same only if one island can be shifted up, down, left, or right to exactly match the other island.
Rotating or reflecting an island is not allowed when comparing island shapes.
Method Signature
int countDistinctIslands(List<String> grid)
- Returns the number of distinct island shapes in the given grid.
- Each string in
grid represents one row of the grid.
- Each character in a row is either
'0' or '1'.
Input Format
grid is a List<String>.- Each string contains only characters
'0' and '1'.
- All strings in
grid have the same length.
'1' represents land.'0' represents water.
Output Format
- Return an integer representing the number of distinct island shapes.
Island Connection Rules
- Land cells are connected only in four directions: up, down, left, and right.
- Diagonal cells are not considered connected.
- Every connected group of land cells forms exactly one island.
Distinct Island Rules
- Two islands are the same if one island can be translated to match the other island exactly.
- Translation means shifting the island without changing its shape.
- Rotation is not allowed.
- Reflection is not allowed.
- If two islands only match after rotation or reflection, they must be counted as different shapes.
Constraints
1 ≤ grid.size() ≤ 501 ≤ grid.get(i).length() ≤ 50grid.get(i).length() == grid.get(0).length() for every valid row index igrid.get(i).charAt(j) is either '0' or '1'grid is non-empty- No parameter value will be
null
Examples
Example 1
countDistinctIslands(grid = List.of("11000", "10000", "00011", "00010"))
Output: 1
Explanation:
The grid contains two islands.
The first island has shape:
11
1
The second island has the same shape after shifting it to another position. Since one island can be translated to match the other, there is only 1 distinct island shape.
Example 2
countDistinctIslands(grid = List.of("11011", "10000", "00001", "11011"))
Output: 3
Explanation:
The grid contains four islands.
The top-left island has shape:
11
1
The top-right island has shape:
11
The bottom-left island has shape:
11
The bottom-right island has shape:
1
11
The top-right and bottom-left islands have the same shape after translation. The top-left island and bottom-right island are different because rotation or reflection is not allowed. Therefore, there are 3 distinct island shapes.
Example 3
countDistinctIslands(grid = List.of("110", "100", "000", "011", "001"))
Output: 2
Explanation:
The first island has shape:
11
1
The second island has shape:
11
1
These two shapes are reflections of each other, but reflection is not allowed. Therefore, they are counted as different island shapes.
Example 4
countDistinctIslands(grid = List.of("000", "000"))
Output: 0
Explanation:
There is no land cell in the grid, so there are no islands.
Example 5
countDistinctIslands(grid = List.of("1"))
Output: 1
Explanation:
The grid contains one island with one land cell, so there is 1 distinct island shape.