01 Matrix

DP

public class Solution {
    public int[][] UpdateMatrix(int[][] matrix) {
        int m = matrix.Length;
        int n = matrix[0].Length;

        int[][] F= new int[m][];

        for(int i = 0 ; i < m ; i++){
            F[i] = Enumerable.Repeat(int.MaxValue - 1, n).ToArray();
        }

        for(int i = 0 ; i < m ; i++){
            for(int j = 0; j < n ; j++){
                if(matrix[i][j] == 1){
                    if(i > 0){
                        F[i][j] = Math.Min(F[i][j],  F[i - 1][j] + 1 );
                    }

                    if(j > 0){
                        F[i][j] = Math.Min(F[i][j], F[i][j - 1] + 1);
                    }
                }
                else{
                    F[i][j] = 0;
                }
            }
        }

        for(int i = m - 1 ; i >= 0 ; i-- ){
            for(int j = n - 1 ; j >= 0; j-- ){
                if(F[i][j] != 0 && F[i][j] != 1 ){
                    if(i < m - 1){
                        F[i][j] = Math.Min(F[i][j], F[i + 1][j] + 1);
                    }

                    if(j < n - 1){
                        F[i][j] = Math.Min(F[i][j], F[i][j + 1] + 1);
                    }
                }

            }

        }

        return  F;

    }
}


BFS

public class Solution {
    public int[][] UpdateMatrix(int[][] matrix) {
        int m = matrix.Length;
        int n = matrix[0].Length;

        Queue<int[]> q = new Queue<int[]>();

        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < n ; j++){
                if(matrix[i][j] == 0){
                    q.Enqueue(new int[]{i, j});
                }
                else{
                    matrix[i][j] = int.MaxValue;
                }
            }
        }

        int[][] dirs = new int[4][];
        dirs[0] = new int[]{-1, 0};
        dirs[1] = new int[]{1, 0};
        dirs[2] = new int[]{0, -1};
        dirs[3] = new int[]{0, 1};

        while(q.Count > 0){
            var curr = q.Dequeue();

            // four directions.
            for(int i = 0 ; i < dirs.Length; i++){
                int x = curr[0] + dirs[i][0];
                int y = curr[1] + dirs[i][1];

                if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <=  matrix[curr[0]][curr[1]] + 1 ){
                    continue;    
                }
                   matrix[x][y] = matrix[curr[0]][curr[1]] + 1 ;
                   q.Enqueue(new int[]{x, y});
              }
        }

        return matrix;

    }
}