Minimum Cells to Bridge a Magic Grid

Problem Statement

You are given an m x n 2D integer array grid, along with starting coordinates start = [sr, sc] and target coordinates target = [tr, tc].

The grid represents a mystical floating realm where each cell (r, c) has a specific property:

• -1: An unstable rift. This cell is completely impassable and cannot be bridged.
• 0: A void cell. Moving onto this cell requires placing 1 bridge cell.
• 1: An ancient magic conduit. Moving onto or across this cell requires 0 bridge cells.
• 2 through 9: A resonance portal. Stepping onto this cell costs 0 bridge cells. Furthermore, all cells sharing the exact same resonance value k (k >= 2) are instantaneously linked; you may teleport between any two cells with the same resonance value at a cost of 0 bridge cells.

From any cell, you can move to its 4-directionally adjacent neighbors (up, down, left, right), provided the neighbor is within grid bounds and not an unstable rift (-1). You may also use resonance portals when currently on a portal cell.

If the initial cell start is a void cell (0), you must place a bridge cell there first (costing 1). Otherwise, starting on a conduit or portal costs 0.

Return the minimum number of bridge cells needed to travel from start to target. If it is impossible to reach target, return -1.

Function Signature

def min_bridge_cells(grid: list[list[int]], start: list[int], target: list[int]) -> int:
    pass

Input Format

• grid: A 2D list of integers of dimensions m x n.
• start: A list of two integers [sr, sc].
• target: A list of two integers [tr, tc].

Output Format

• An integer representing the minimum number of bridge cells required, or -1 if unreachable.

Constraints

• m == len(grid)
• n == len(grid[0])
• 1 <= m, n <= 500
• grid[r][c] in [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
• 0 <= sr, tr < m
• 0 <= sc, tc < n

Examples

Example 1

Input:
grid = [
  [1, 0, -1],
  [0, 2,  0],
  [-1, 0, 2]
]
start = [0, 0]
target = [2, 2]

Output: 1

Explanation:
- Start at (0, 0) which is a conduit (cost = 0).
- Move down to (1, 0), placing 1 bridge cell (cost = 1).
- Move right to (1, 1), which is resonance portal 2 (cost = 1).
- Teleport from (1, 1) to (2, 2), which also has resonance portal 2 (cost = 1).
Total bridge cells used: 1.

Example 2

Input:
grid = [
  [0, -1],
  [-1, 1]
]
start = [0, 0]
target = [1, 1]

Output: -1

Explanation:
All paths from (0, 0) to (1, 1) are blocked by unstable rifts (-1).

Edge Cases

• start == target: The answer is 1 if grid[sr][sc] == 0, and 0 if grid[sr][sc] >= 1 (or -1 if it is an impassable cell -1).
• grid[sr][sc] == -1 or grid[tr][tc] == -1: Impossible from the beginning, return -1.
• Multiple portals of the same value: Ensure teleportation edges do not cause redundant quadratic iterations.