[LeetCode] 317. Shortest Distance from All Buildin

wall2flower 发布于2019-08-16 13:44 / 1203人阅读

Problem

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.
Example:

Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 7

Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2),

         the point (1,2) is an ideal empty land to build a house, as the total 
         travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

Solution

class Solution {
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return -1;
        int m = grid.length, n= grid[0].length;
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) count++;
            }
        }
        
        int[][] dist = new int[m][n];
        int[][] conn = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    if (!bfs(grid, i, j, count, dist, conn)) return -1;
                }
            }
        }
        
        int min = Integer.MAX_VALUE;
        boolean found = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    if (conn[i][j] == count) {
                        found = true;
                        min = Math.min(min, dist[i][j]);
                    }
                }
            }
        }
        return found ? min : -1;
    }
    
    class Point {
        int x;
        int y;
        int distance;
        Point(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.distance = dist;
        }
    }
    
    private boolean bfs(int[][] grid, int xstart, int ystart, int count, int[][] dist, int[][] conn) {
        boolean[][] spot = new boolean[grid.length][grid[0].length];
        Deque queue = new ArrayDeque<>();
        queue.offer(new Point(xstart, ystart, 0));
        spot[xstart][ystart] = true;
        int buildings = 1;
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = cur.x + dx[i];
                int y = cur.y + dy[i];
                if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) continue;
                //connect to a building
                if (grid[x][y] == 1 && !spot[x][y]) {
                    spot[x][y] = true;
                    buildings++;
                }
                //connect to a spot
                if (grid[x][y] == 0 && !spot[x][y]) {
                    spot[x][y] = true;
                    queue.offer(new Point(x, y, cur.distance+1));
                    dist[x][y] += cur.distance+1;
                    conn[x][y]++;
                }
            }
        }
        return buildings == count;
    }
}

GPU云服务器云服务器 Shortest Distance LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72256.html

leetcode 317 shortest distance from all buildings

摘要：从第一个点出发表示空地，表示已经走过的空地，避免重复。看起来就像一层层的涂色。 1 0 2 0 1 0 0 0 0 0 0 0 1 0 0 第一个building, 把涂色把0变成-1, 同一层最终会涂成相同颜色-1 1 -1 2 -1 1 -1 -1 -1 -1 -1 -1 ...

yanbingyun1990 2019-08-14 17:38 评论0 收藏0
Shortest Distance from All Buildings

摘要：如果该没有被之前所有的访问过，就不可能成为答案根据要求的位置能到所有的，其他与它相邻的点也是这样。和用矩阵比，缩小了每次遍历的范围。 Shortest Distance from All Buildings 题目链接：https://leetcode.com/problems... 这道题要求最短的距离，一般这种要求可以到的地方的距离，都需要把整个图遍历一遍，遍历一般就是bfs和dfs...

DC_er 2019-08-14 17:18 评论0 收藏0
[LeetCode] 126. Word Ladder II

摘要：存放过程中的所有集合为所有的结尾，则顺序存放这个结尾对应的中的所有存放同一个循环的新加入的，在下一个循环再依次对其中元素进行进一步的把首个字符串放入新，再将放入，并将键值对放入，进行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...

wayneli 2019-08-14 14:27 评论0 收藏0
[LeetCode] Shortest Distance to a Character

Problem Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string. Example 1: Input: S = loveleetcode, C = eOutput: [3, 2, 1...

blankyao 2019-08-19 11:00 评论0 收藏0
[Leetcode] Shortest Word Distance 最短单词间距

摘要：代码第一次写入就先不比较第一次写入就先不比较哈希表法复杂度时间空间思路因为会多次调用，我们不能每次调用的时候再把这两个单词的下标找出来。我们可以用一个哈希表，在传入字符串数组时，就把每个单词的下标找出存入表中。 Shortest Word Distance Given a list of words and two words word1 and word2, return the ...

jsliang 2019-08-14 12:48 评论0 收藏0