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 1s.

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.