Share a Java implement


  • 29

    Short version: BFS from every building, calculate the distances and find the minimum distance in the end.

    Key optimization : we do not go into a land, if it is not accessible by at least one of previous buildings.

    For a long explanation see here in my blog.

    It runs in 13 ms.

    It is the same idea as stefan's c++ solution. I didn't see it until now. I did this myself.

    Also one may want to make a copy of grid if it is not suppose to be modified.

    Java

    int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
    
    public int shortestDistance(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        // Initialize building list and accessibility matrix `grid`
        List<Tuple> buildings = new ArrayList<>();
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1)
                    buildings.add(new Tuple(i, j, 0));
                grid[i][j] = -grid[i][j];
            }
        // BFS from every building
        for (int k = 0; k < buildings.size(); ++k)
            bfs(buildings.get(k), k, dist, grid, m, n);
        // Find the minimum distance
        int ans = -1;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == buildings.size() && (ans < 0 || dist[i][j] < ans))
                    ans = dist[i][j];
        return ans;
    }
    
    public void bfs(Tuple root, int k, int[][] dist, int[][] grid, int m, int n) {
        Queue<Tuple> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            Tuple b = q.poll();
            dist[b.y][b.x] += b.dist;
            for (int i = 0; i < 4; ++i) {
                int x = b.x + dx[i], y = b.y + dy[i];
                if (y >= 0 && x >= 0 && y < m && x < n && grid[y][x] == k) {
                    grid[y][x] = k + 1;
                    q.add(new Tuple(y, x, b.dist + 1));
                }
            }
        }
    }
    class Tuple {
        public int y;
        public int x;
        public int dist;
    
        public Tuple(int y, int x, int dist) {
            this.y = y;
            this.x = x;
            this.dist = dist;
        }
    }
    // 72 / 72 test cases passed.
    // Status: Accepted
    // Runtime: 13 ms
    // 99.22%

  • 0
    J

    Awesome optimization!


  • 0

    your link of blog is not working now. I really want to see it. It has always been a good place to study. Will you please fix the blog. I appreciate it.


  • 0

    I updated the wordpress theme...and then it crashed...
    No idea why....


  • 0

    it says algobox.org is currently unable to handle this request


  • 0

    yes i know. I am working on it.


  • 0

    It's ok now.


  • 0
    I

    Its again down and it says "Error establishing a database connection"


  • 0
    T

    @dietpepsi When I click the link to your blog, a page showed up asking for password to log in. Do you mind for telling me how to access your blog? I would like to see your explanation for this problem. Thanks!


  • 0

    Why did u write it in this way dist[b.y][b.x] += b.dist;? Why no just x, y instead of y, x? Is there any special meaning in it?

    Basically, in BFS, you reversed all x and y, because you use x to be y and y to be x in Tuple, I cannot figure out why.


  • 0

    @zhugejunwei Same question


  • 0
    B

    @dietpepsi said in Share a Java implement:

    grid[y][x] == k

    This is my favorite part of this code, which can not only eliminates unnecessary exploration of grids that cannot be reached by any of previous buildings, but also avoid using boolean[][] visited array to record visited grids. Thanks a lot :)


  • 0

    @bobw Can you explain the purpose of this equation? I'm not sure I get the point. Is it used to count the number of reachable buildings so far(not all, only the previous ones)?


Log in to reply
 

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