Shortest Distance from All Buildings

DC_er 發布于2019-08-14 17:18 / 3077人閱讀

摘要：如果該沒有被之前所有的訪問過，就不可能成為答案根據要求的位置能到所有的，其他與它相鄰的點也是這樣。和用矩陣比，縮小了每次遍歷的范圍。

Shortest Distance from All Buildings

題目鏈接：https://leetcode.com/problems...

這道題要求最短的距離，一般這種要求可以到的地方的距離，都需要把整個圖遍歷一遍，遍歷一般就是bfs和dfs。這道題不用dfs的原因是：empty的位置到building的距離是按最小值來算的，用dfs每次如果放入depth不一定是最小的距離，每次都得更新，沒有效率。這道題用bfs的原因：一樣的原因，因為距離就是按照最小的距離來算的，完全是bfs的思路。
visited一般兩種方式：用一個boolean的矩陣，直接改寫grid的值。這里用第二種。-grid[i] [j]表示(i, j)點可以reach到的building數目。當grid[i] [j] == # of buildings so far時，證明當前點還沒被visited，且當前點被之前所有的buildings都visited過，那么每次bfs只訪問這些點。如果該point沒有被之前所有的buildings訪問過，就不可能成為答案（根據要求empty的位置能到所有的buildings），其他與它相鄰的點也是這樣。和用boolean矩陣比，縮小了每次遍歷的范圍。
從每一個building，即grid[i] [j] == 1的點開始做bfs層次遍歷。

用一個distance矩陣來記錄(i, j)到所有building的距離和，對每一個building做bfs

每次bfs的時候，更新distance[i] [j]的值:

Queue 記錄point

更新level += 1

go over當前level的全部point

if (i, j)在圖內&grid[i] [j] = -num:

distance[i] [j] += level

grid[i] [j] --

q.offer(i, j)

go over整個distance數組，當-grid[i] [j] == # of buildings時，更新最小的距離值

public class Solution {
    public int shortestDistance(int[][] grid) {
        /* approach: bfs, distance array
         * for each building, do a bfs, add the distance
         * variable: num: record number of buildings already searched
         * visited => use the grid => do -- if visited[i][j] = -num
         * result: the grid[i][j] == -(number of buildings) is the possible
         *         find the smallest distance[i][j]
         */
         distance = new int[grid.length][grid[0].length];
         int num = 0;
         for(int i = 0; i < grid.length; i++) {
             for(int j = 0; j < grid[0].length; j++) {
                 if(grid[i][j] == 1) {
                     bfs(grid, i, j, -num);
                     num++;
                 }
             }
         }
         int result = Integer.MAX_VALUE;
         // find the smallest distance
         for(int i = 0; i < grid.length; i++) {
             for(int j = 0; j < grid[0].length; j++) {
                 if(grid[i][j] == -num) result = Math.min(result, distance[i][j]);
             }
         }
         return result == Integer.MAX_VALUE ? -1 : result;
    }
    
    int[][] distance;
    int[] dx = new int[] {-1, 1, 0, 0};
    int[] dy = new int[] {0, 0, -1, 1};
    private void bfs(int[][] grid, int x, int y, int num) {
        Queue q = new LinkedList();
        q.offer(new int[] {x, y});
        int len = 0;
        while(!q.isEmpty()) {
            len++;
            // current level
            for(int j = q.size(); j > 0; j--) {
                int[] cur = q.poll();
                // 4 directions
                for(int i = 0; i < 4; i++) {
                    int nx = cur[0] + dx[i], ny = cur[1] + dy[i];
                    if(nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] == num) {
                        distance[nx][ny] += len;
                        q.offer(new int[] {nx, ny});
                        grid[nx][ny]--;
                    }
                }
            }
        }
    }
}

云服務器 GPU云服務器 Buildings Shortest Distance All

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66556.html

[LeetCode] 317. Shortest Distance from All Buildin

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...

wall2flower 2019-08-16 13:44 評論0 收藏0
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
LeetCode[218] The Skyline Problem

摘要：復雜度思路利用的思想，先分成左右兩部分，再進行。每次都要將的左上角和右下角推進，進行計算。觀察左邊和右邊進行。 LeetCode[218] The Skyline Problem A citys skyline is the outer contour of the silhouette formed by all the buildings in that city when vie...

keithyau 2019-08-14 15:57 評論0 收藏0
Walls and Gates

摘要：題目鏈接這道題感覺是那道的簡化版，思路都是一樣的。是把所有的點都先放到里面，然后一起遍歷。這種寫法的好處是保證了每個點都只被放進一次，不會重復遍歷。保證了時間復雜是。可以不寫成層次遍歷的形式，直接，的程序 Walls and Gates 題目鏈接：https://leetcode.com/problems... 這道題感覺是那道Shortest Distance from All Bu...

CKJOKER 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