Compute Nearest Destination Distances

Problem Statement

You are given a 2D grid of size m x n consisting of three types of cells:

• 0: An empty space that you can move through.
• 1: An obstacle that you cannot enter.
• 2: A destination.

Your task is to return a grid of the same dimensions where each cell contains the shortest distance from that cell to the nearest destination. If a cell is an obstacle, mark it as -1. If an empty cell is unreachable from any destination, mark it as -1.

You can move up, down, left, or right. Each move has a cost of 1.

Function Signature

def nearest_destination(grid: List[List[int]]) -> List[List[int]]:

Examples

Example 1: Input: grid = [[0, 0, 0], [0, 1, 0], [0, 0, 2]] Output: [[4, 3, 2], [3, -1, 1], [2, 1, 0]]

Example 2: Input: grid = [[2, 0], [1, 1]] Output: [[0, 1], [-1, -1]]

Constraints

• m == grid.length
• n == grid[0].length
• 1 <= m, n <= 500
• grid[i][j] is either 0, 1, or 2.