Funcia
Lv.2bfsdfsgridhash

Distinct Island Shapes

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

gridresult
["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

  • 1≤H=1 \le H = grid.length ≤1,000\le 1{,}000
  • 1≤W=1 \le W = grid[i].length ≤1,000\le 1{,}000; all rows have the same length.
  • grid[i] consists only of '0' and '1'.

Expected complexity

Time
O(HW)
Space
O(HW)

Examples

gridExpected
["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 10610^6 cells.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251184 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.