The solution is based on a couple of other solutions in this topic. It beats 100% C# solution as of now. The translated Java version runs in 16ms. The reason I put here is because few ppl posted C# solutions.

Algorithm:

- BFS starting from each building
- do level traversal. Add the level(i.e. distance) to the 2-D distance array
- optimization: change each land to mark (initially 0, then -1, -2, ...) so it can skip lands one of the previous buildings can't reach. By doing so we don't need the array visited[,]

```
public int ShortestDistance(int[,] grid)
{
int[] dx = new int[] { -1, 1, 0, 0 };
int[] dy = new int[] { 0, 0, -1, 1 };
int m = grid.GetLength(0);
int n = grid.GetLength(1);
int[,] dist = new int[m, n];
int mark = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i, j] == 1)
{
Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();
queue.Enqueue(new Tuple<int, int>(i, j));
int level = 1;
while (queue.Count > 0)
{
int size = queue.Count;
for (int k = 0; k < size; k++)
{
var tuple = queue.Dequeue();
for (int l = 0; l < dx.Length; l++)
{
int x = dx[l] + tuple.Item1;
int y = dy[l] + tuple.Item2;
if (x >= 0 && x < m && y >= 0 && y < n && grid[x, y] == mark)
{
dist[x, y] += level;
grid[x, y]--;
queue.Enqueue(new Tuple<int, int>(x, y));
}
}
}
level++;
}
mark--; // this line should be in if block
}
}
}
int minDist = -1; // this is the value which should be returned if no solution
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i, j] == mark)
{
minDist = minDist < 0 ? dist[i, j] : Math.Min(minDist, dist[i, j]);
}
}
}
return minDist;
}
```

Translated Java Version. A few notes for the translation

- Java does not have built-in class Tuple so create one
- C# 2-D array [,] or [][], Java [][]
- C# Queue class, Enqueue()/Dequeue(); Java uses LinkedList, offer()/poll()
- C# Tuple<int,int>, Java Tuple<Integer, Integer>

```
public class Solution
{
public class Tuple<X, Y>
{
public final X x;
public final Y y;
public Tuple(X x, Y y)
{
this.x = x;
this.y = y;
}
}
public int shortestDistance(int[][] grid)
{
int[] dx = new int[] { -1, 1, 0, 0 };
int[] dy = new int[] { 0, 0, -1, 1 };
int m = grid.length;
int n = grid[0].length;
int[][] dist = new int[m][n];
int mark = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 1)
{
Queue<Tuple<Integer, Integer>> queue = new LinkedList<Tuple<Integer, Integer>>();
queue.offer(new Tuple<Integer, Integer>(i, j));
int level = 1;
while (!queue.isEmpty())
{
int size = queue.size();
for (int k = 0; k < size; k++)
{
Tuple<Integer, Integer> tuple = queue.poll();
for (int l = 0; l < dx.length; l++)
{
int x = dx[l] + tuple.x;
int y = dy[l] + tuple.y;
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == mark)
{
dist[x][y] += level;
grid[x][y]--;
queue.offer(new Tuple<Integer, Integer>(x, y));
}
}
}
level++;
}
mark--;
}
}
}
int minDist = -1; // this is the value which should be returned if no solution
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == mark)
{
minDist = minDist < 0 ? dist[i][j] : Math.min(minDist, dist[i][j]);
}
}
}
return minDist;
}
}
```