using System;

using System.Collections.Generic;

public class Solution {

public int[][] UpdateMatrix(int[][] mat) {

    int rows = mat.Length;

    int cols = mat[0].Length;

    

    // Create result matrix

    int[][] result = new int[rows][];

    for (int i = 0; i < rows; i++) {

        result[i] = new int[cols];

    }

    

    // Queue for BFS - stores (row, col)

    Queue<(int row, int col)> queue = new Queue<(int, int)>();

    

    // Initialize: Add all 0s to queue and mark others as -1 (unvisited)

    for (int i = 0; i < rows; i++) {

        for (int j = 0; j < cols; j++) {

            if (mat[i][j] == 0) {

                result[i][j] = 0;

                queue.Enqueue((i, j));

            } else {

                result[i][j] = -1; // Mark as unvisited

            }

        }

    }

    

    // Directions: up, down, left, right

    int[][] directions = new int[][] {

        new int[] {-1, 0}, // up

        new int[] {1, 0},  // down

        new int[] {0, -1}, // left

        new int[] {0, 1}   // right

    };

    

    // BFS to find shortest distances

    while (queue.Count > 0) {

        var (row, col) = queue.Dequeue();

        

        // Check all 4 directions

        foreach (var dir in directions) {

            int newRow = row + dir[0];

            int newCol = col + dir[1];

            

            // Check bounds and if cell is unvisited

            if (newRow >= 0 && newRow < rows && 

                newCol >= 0 && newCol < cols && 

                result[newRow][newCol] == -1) {

                

                // Set distance = current distance + 1

                result[newRow][newCol] = result[row][col] + 1;

                queue.Enqueue((newRow, newCol));

            }

        }

    }

    

    return result;

}

}