Distinct Island Shapes
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
You are given a sea map grid: character j of grid[i] is '1' for land and '0' for water. Land cells connected
horizontally or vertically form one island (cells touching only diagonally belong to different islands).
Two islands have the same shape if one can be moved onto the other by translation only; islands that match only after a
rotation or reflection are different. Return the number of distinct island shapes, or 0 if there is no island.
Examples
| grid | result |
|---|---|
["11000", "11000", "00011", "00011"] | 1 |
["11011", "10000", "00001", "11011"] | 3 |
["010", "101", "010"] | 1 |
Example 1 — Two 2×2 squares: one shape.
Example 2 — Four islands. The two horizontal dominoes match. The ┌-shaped island and the ┘-shaped island only match
after a rotation, so they are different: 3 shapes.
Example 3 — Four single-cell islands touching only diagonally: one shape.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(grid: string[]) → int
Constraints
-
grid.length -
grid[i].length; all rows have the same length. grid[i]consists only of'0'and'1'.
Expected complexity
- Time
- O(HW)
- Space
- O(HW)
Examples
| grid | Expected |
|---|---|
["11000","11000","00011","00011"] | 1 |
["11011","10000","00001","11011"] | 3 |
["010","101","010"] | 1 |
Hint
Hint
Give every island a translation-independent signature and put it in a hash set. Start BFS at the first land cell (r0, c0) in
row-major order and record (r - r0, c - c0) for each visited cell; with a fixed neighbour order, equal shapes produce equal
lists. Comparing each new island with every shape found so far is too slow when there are many islands. Use an iterative
BFS/DFS: the grid can have cells.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1184 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |