leetcode 317 shortest distance from all buildings

yanbingyun1990 發布于2019-08-14 17:38 / 3484人閱讀

摘要：從第一個點出發表示空地，表示已經走過的空地，避免重復。看起來就像一層層的涂色。

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

距離矩陣

0   1   0   5   0

1   2   3   4   5

2   3   0   5   6

第一個building, 把涂色把-1變成-2, 同一層最終會涂成相同顏色-2

  1    -2    2   -2    1  

 -2    -2   -2   -2   -2

 -2    -2    1   -2   -2

距離矩陣

0   6   0   6   0

6   6   6   6   6

8   8   0   8   8

第一個building, 把涂色把-2變成-3, 同一層最終會涂成相同顏色-3

  1    -3    2   -3    1  

 -3    -3   -3   -3   -3

 -3    -3    1   -3   -3

距離矩陣

0    9    0   9   0

9    8    7   8   9

10   9    0   9   10

為了避路徑重復，我們有兩種方法，一種是用額外的空間visited, 一種是改變輸入。
從第一個點出發0表示空地，-1表示已經走過的空地，避免重復。
從第二個點出發-1表示空地，-2表示已經走過的空地，避免重復。
看起來就像一層層的涂色。

public class Solution {
    private int[] dx = {0, 1, 0, -1},  dy = {1, 0, -1, 0};
    private int min = Integer.MAX_VALUE;
    
    public int shortestDistance(int[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        int m = grid.length, n = grid[0].length;
        int[][] distance = new int[m][n];                   // 記錄累加距離
        int start = 0;
        for(int i=0; i q = new ArrayDeque<>();
         q.offer(new int[]{i,j});                           
         int level = 0, m = grid.length, n = grid[0].length;
         min = Integer.MAX_VALUE;
         
         while(!q.isEmpty()){
             int size = q.size();                       // 涂色的時候，記錄當前層的大小
             level++;                                   // 進入下一層，需要增加距離
             for(int k=0; k=0 && y>=0 && x

云服務器 GPU云服務器 Shortest Distance Leetcod LeetCode

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66713.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
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