Solve two grid problems (islands + min-cost path)

You are given two separate coding questions. ## Problem A: Count distinct islands (translation-equivalent) Given an `m x n` binary grid `grid` (0 = water, 1 = land), an **island** is a maximal 4-directionally connected group of `1`s. 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. **Task:** Return the number of **distinct** island shapes in the grid. **Input:** `grid: List[List[int]]` **Output:** `int` **Notes/constraints (assume typical interview constraints):** - `1 <= m, n <= 500` - Grid can be large; aim for about `O(mn)` time. --- ## Problem B: Minimum cost to create a valid path in a directed grid You are given an `m x n` grid `dir` where each cell contains a direction pointing to a neighbor: - `1` = right, `2` = left, `3` = down, `4` = up Starting at `(0,0)`, if you follow directions, you move to the indicated neighboring cell (if within bounds). A **valid path** is a path that reaches `(m-1, n-1)`. You may **change** the direction in any cell at a cost of `1` per changed cell (each cell can be changed to any of the 4 directions). **Task:** Return the minimum total cost to ensure there exists at least one valid path from `(0,0)` to `(m-1,n-1)`. **Input:** `dir: List[List[int]]` **Output:** `int` **Notes/constraints (assume typical interview constraints):** - `1 <= m, n <= 1000` - Aim for near-linear time in number of cells.