C# Solution, BFS


  • 1
    B
    public class Solution 
    {
        public int[,] UpdateMatrix(int[,] matrix) 
        {
            var row = matrix.GetLength(0);
            var col = matrix.GetLength(1);
    
            if (row == 0) return new int[0,0];
            
            var result = new int[row,col];
    
           for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    if (matrix[i, j] == 0) continue;
                    
                    var distance = UpdateMatrixBFS(matrix, i, j);
                    result[i, j] = distance;
                }
            }
    
            return result;
        }
    
        private int UpdateMatrixBFS(int[,] matrix, int startX, int startY)
        {
            var row = matrix.GetLength(0);
            var col = matrix.GetLength(1);
    
            var directions = new int[,]{{0,1}, {0,-1}, {1,0}, {-1,0}};
    
            var queue = new Queue<Tuple<int,int>>();
    
            queue.Enqueue(Tuple.Create(startX, startY));
            var distance = 1;
            while(queue.Any())
            {
                var size = queue.Count;
    
                for (int z = 0; z < size; z++)
                {
                    var cur = queue.Dequeue();
    
                    for(int i = 0; i < directions.GetLength(0); i++)
                    {
                        var directionX = directions[i,0];
                        var directionY = directions[i,1];
    
                        var nextX = cur.Item1 + directionX;
                        var nextY = cur.Item2 + directionY;
    
                        if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) continue;
                        
                        if (matrix[nextX, nextY] == 0) return distance;
                        
                        queue.Enqueue(Tuple.Create(nextX, nextY));
                    }
                }
    
                distance++;
            }
    
            return distance;
        }
    }
    

  • 0
    N

    @bacon very nice


  • 0
    V

    I think it's not an efficient algorithm.
    For worst case suppose only 1 zero that too in matrix[0][0] position, in that case, your algo will work in O(nmmax(n,m))** which is not efficient and desirable. I wonder can you do with bfs only in O (nm)* ?


  • 0
    B

    @vaibhav15 You are right. I think if I check the min distance for each result which can save the time. But for this question, I prefer the DP solution now. Please check this:

    public class Solution 
    {
        public int[,] UpdateMatrix(int[,] matrix) 
        {
            var row = matrix.GetLength(0);
            var col = matrix.GetLength(1);
    
            var dp = new int[row, col];
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    dp[i, j] = int.MaxValue - 10000;
                }
            }
    		
            // TOP-LEFT
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    if (matrix[i, j] == 0)
                    {
                        dp[i, j] = 0;
                    }
                    else
                    {
                        if (i > 0) dp[i, j] = Math.Min(dp[i, j], dp[i-1, j] + 1);
                        if (j > 0) dp[i, j] = Math.Min(dp[i, j], dp[i, j-1] + 1);
                    }
                }
            }
    		
            // BOTTOM-RIGHT
            for (int i = row - 1; i >= 0; i--)
            {
                for (int j = col - 1; j >= 0; j--)
                {
                    if (i < row - 1) dp[i, j] = Math.Min(dp[i, j], dp[i+1, j] + 1);
                    if (j < col - 1) dp[i, j] = Math.Min(dp[i, j], dp[i, j+1] + 1);
                }
            }
    
            return dp;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.