Given an `m x n` binary matrix `mat`, return _the distance of the nearest_ `0` _for each cell_.

The distance between two adjacent cells is `1`.

**Example 1:**

**Input:** mat = \[\[0,0,0\],\[0,1,0\],\[0,0,0\]\]
**Output:** \[\[0,0,0\],\[0,1,0\],\[0,0,0\]\]

**Example 2:**

**Input:** mat = \[\[0,0,0\],\[0,1,0\],\[1,1,1\]\]
**Output:** \[\[0,0,0\],\[0,1,0\],\[1,2,1\]\]

**Constraints:**

*   `m == mat.length`
*   `n == mat[i].length`
*   `1 <= m, n <= 104`
*   `1 <= m * n <= 104`
*   `mat[i][j]` is either `0` or `1`.
*   There is at least one `0` in `mat`.


from collections import deque


def updateMatrix(mat):
    m, n = len(mat), len(mat[0])
    distance = [[0 if mat[i][j] == 0 else float('inf') for j in range(n)] for i in range(m)]
    queue = deque([(i, j) for i in range(m) for j in range(n) if mat[i][j] == 0])

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            newX, newY = x + dx, y + dy
            if 0 <= newX < m and 0 <= newY < n and distance[newX][newY] > distance[x][y] + 1:
                distance[newX][newY] = distance[x][y] + 1
                queue.append((newX, newY))

    return distance
