# C# Solution, BFS

• ``````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;
}
}
``````

• @bacon very nice

• 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)* ?

• @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;
}
}
``````

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