Count islands using BFS without modifying grid

You are given an m x n binary grid grid where:

• 1 represents land
• 0 represents water
• Islands are groups of horizontally or vertically adjacent land cells (4-directional connectivity).

Part A

Return the number of islands in the grid.

Constraint: You must solve it using BFS, and you are not allowed to modify grid in-place (e.g., you cannot flip visited 1s to 0s).

Part B (follow-up)

Two islands are considered the same shape if one can be translated (shifted up/down/left/right) to match the other exactly (rotations/reflections do not count unless explicitly stated).

Return the number of distinct island shapes in the grid.

Input/Output

• Input: grid: List[List[int]]
• Output (Part A): integer count of islands
• Output (Part B): integer count of distinct island shapes

Assumptions / Constraints

• 1 <= m, n <= 200 (or similar)
• Time should be near O(mn)
• Extra space allowed for visited tracking and shape encoding

Count Islands using BFS (without modifying the grid)

You are given an m x n binary grid grid where 1 represents land and 0 represents water. Islands are groups of horizontally or vertically adjacent land cells (4-directional connectivity).

Return the number of islands in the grid.

Constraints on your approach:

• You must solve it using BFS (breadth-first search).
• You are not allowed to modify grid in-place (you cannot flip visited 1s to 0s). Use a separate visited structure to track explored cells.

Input/Output

• Input: grid: List[List[int]]
• Output: integer count of islands

Examples

Example 1

Input: ([[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]],)
Output: 3

Explanation: Top-left 2x2 block (1 island), the single 1 at (2,2), and the horizontal pair at (3,3)-(3,4) = 3 islands.

Example 2

Input: ([[1,1,1],[0,1,0],[1,1,1]],)
Output: 1

Explanation: All land cells are connected through the center column into one island.

Hints

1. Scan every cell. When you hit a land cell that hasn't been visited yet, you've found a new island — increment your count and BFS-flood the whole island.
2. Because you can't overwrite the grid, keep a parallel boolean visited[m][n] matrix and mark cells there as you enqueue them.
3. Mark a cell visited at enqueue time (not dequeue time) so the same cell is never added to the queue twice.

Count Distinct Island Shapes (translation-invariant)

You are given an m x n binary grid grid where 1 represents land and 0 represents water. Islands are groups of horizontally or vertically adjacent land cells (4-directional connectivity).

Two islands are considered the same shape if one can be translated (shifted up/down/left/right) to match the other exactly. Rotations and reflections do not count as the same shape.

Return the number of distinct island shapes in the grid.

Constraints on your approach:

• Use BFS to discover each island.
• Do not modify grid in-place; use a separate visited structure.

Input/Output

• Input: grid: List[List[int]]
• Output: integer count of distinct island shapes

Examples

Example 1

Input: ([[1,1,0,0],[1,0,0,0],[0,0,1,1],[0,0,1,0]],)
Output: 1

Explanation: Both islands are the same L-tromino shape after translation, so there is 1 distinct shape.

Example 2

Input: ([[1,1,0,1,1],[0,0,0,0,0],[1,1,0,1,0],[1,0,0,1,0]],)
Output: 3

Explanation: Two horizontal dominoes (same shape), one L-tromino, and one vertical domino -> distinct shapes are {horizontal domino, L-tromino, vertical domino} = 3.

Hints

1. Collect every cell of an island during BFS, then convert that set of coordinates into a translation-invariant signature.
2. To make the signature translation-invariant, subtract the island's minimum row and minimum column from every cell so each island is re-anchored to (0,0).
3. Sort the normalized coordinate list and store it (as a tuple/string) in a set. The answer is the size of the set. Sorting guarantees two islands discovered in different orders produce identical keys.