C# solution which beats 100% other C# solutions. Translated Java version runs in 16ms


  • 0
    E

    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:

    1. BFS starting from each building
    2. do level traversal. Add the level(i.e. distance) to the 2-D distance array
    3. 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

    1. Java does not have built-in class Tuple so create one
    2. C# 2-D array [,] or [][], Java [][]
    3. C# Queue class, Enqueue()/Dequeue(); Java uses LinkedList, offer()/poll()
    4. 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;
        }
    
    }
    

Log in to reply
 

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