Solve Matrix and Array Distance Problems

Warehouse Proximity Grid

You are managing a distributed database cluster arranged in an m x n grid. Each cell in the grid contains one of three values:

• 'W': An active data warehouse.
• 'C': A compute node that needs to access data.
• 'X': An offline or blocked node that cannot be traversed.

A compute node can communicate with adjacent cells in four cardinal directions (up, down, left, right). Each step between adjacent traversable cells costs 1 unit of latency.

Write a function nearestWarehouseDistances(grid: list[list[str]]) -> list[list[int]] that returns an m x n matrix of integers where:

• The distance for each warehouse cell 'W' is 0.
• The distance for each blocked cell 'X' is -1.
• The distance for each compute node 'C' is the minimum latency (shortest path) to reach any active warehouse 'W'.
• If a compute node cannot reach any warehouse, its distance is -1.

Input and Output Format

• Input: grid, a 2D list of strings of size m x n.
• Output: A 2D list of integers of size m x n containing the shortest distances.

Constraints

• 1 <= m, n <= 1000
• 1 <= m * n <= 5 * 10^5
• grid[r][c] is either 'W', 'C', or 'X'.

Examples

Example 1

Input: grid = [
  ["C", "X", "W"],
  ["C", "C", "C"],
  ["W", "X", "C"]
]
Output: [
  [3, -1,  0],
  [2,  1,  1],
  [0, -1,  2]
]

Explanation: grid[0][0] reaches grid[2][0] in 3 steps: (0,0) -> (1,0) -> (1,1) -> (1,2) -> (0,2) is 4 steps, but (0,0) -> (1,0) -> (2,0) is blocked at (2,1)? Wait: grid[0][0] to grid[1][0] to grid[2][0] is 2 steps. Here grid[2][0] is 'W', so distance is 2. (Note: in the output, grid[0][0] is at (0,0), moving to (1,0) and then (2,0) requires 2 steps).

Let's verify:

• (0,0): goes to (1,0) then (2,0) (W) -> distance 2.
• (1,0): adjacent to (2,0) (W) -> distance 1.
• (1,1): adjacent to (1,2) which is adjacent to (0,2) (W) -> distance 2.

Correct output for this grid:

Input: grid = [
  ["C", "X", "W"],
  ["C", "C", "C"],
  ["W", "X", "C"]
]
Output: [
  [2, -1,  0],
  [1,  2,  1],
  [0, -1,  2]
]

Example 2

Input: grid = [
  ["C", "X"],
  ["X", "C"]
]
Output: [
  [-1, -1],
  [-1, -1]
]

Explanation: There are no warehouses in the grid, so all reachable and unreachable compute nodes return -1.

Edge Cases

• No warehouses present in the grid: all compute nodes should be -1.
• No compute nodes present (only warehouses and obstacles): return 0 for warehouses and -1 for obstacles.
• Disconnected components caused by obstacles surrounding compute nodes.