資訊專欄INFORMATION COLUMN
摘要：如果該沒(méi)有被之前所有的訪問(wèn)過(guò)，就不可能成為答案根據(jù)要求的位置能到所有的，其他與它相鄰的點(diǎn)也是這樣。和用矩陣比，縮小了每次遍歷的范圍。
Shortest Distance from All Buildings
題目鏈接：https://leetcode.com/problems...
這道題要求最短的距離，一般這種要求可以到的地方的距離，都需要把整個(gè)圖遍歷一遍，遍歷一般就是bfs和dfs。這道題不用dfs的原因是：empty的位置到building的距離是按最小值來(lái)算的，用dfs每次如果放入depth不一定是最小的距離，每次都得更新，沒(méi)有效率。這道題用bfs的原因：一樣的原因，因?yàn)榫嚯x就是按照最小的距離來(lái)算的，完全是bfs的思路。
visited一般兩種方式：用一個(gè)boolean的矩陣，直接改寫grid的值。這里用第二種。-grid[i] [j]表示(i, j)點(diǎn)可以reach到的building數(shù)目。當(dāng)grid[i] [j] == # of buildings so far時(shí)，證明當(dāng)前點(diǎn)還沒(méi)被visited，且當(dāng)前點(diǎn)被之前所有的buildings都visited過(guò)，那么每次bfs只訪問(wèn)這些點(diǎn)。如果該point沒(méi)有被之前所有的buildings訪問(wèn)過(guò)，就不可能成為答案（根據(jù)要求empty的位置能到所有的buildings），其他與它相鄰的點(diǎn)也是這樣。和用boolean矩陣比，縮小了每次遍歷的范圍。
從每一個(gè)building，即grid[i] [j] == 1的點(diǎn)開始做bfs層次遍歷。
用一個(gè)distance矩陣來(lái)記錄(i, j)到所有building的距離和，對(duì)每一個(gè)building做bfs
每次bfs的時(shí)候，更新distance[i] [j]的值:
Queue
更新level += 1
go over當(dāng)前l(fā)evel的全部point
if (i, j)在圖內(nèi)&grid[i] [j] = -num:
distance[i] [j] += level
grid[i] [j] --
q.offer(i, j)
go over整個(gè)distance數(shù)組，當(dāng)-grid[i] [j] == # of buildings時(shí)，更新最小的距離值
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]--;
}
}
}
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66556.html
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...
摘要：從第一個(gè)點(diǎn)出發(fā)表示空地，表示已經(jīng)走過(guò)的空地，避免重復(fù)。看起來(lái)就像一層層的涂色。 1 0 2 0 1 0 0 0 0 0 0 0 1 0 0 第一個(gè)building, 把涂色把0變成-1, 同一層最終會(huì)涂成相同顏色-1 1 -1 2 -1 1 -1 -1 -1 -1 -1 -1 ...
摘要：復(fù)雜度思路利用的思想，先分成左右兩部分，再進(jìn)行。每次都要將的左上角和右下角推進(jìn)，進(jìn)行計(jì)算。觀察左邊和右邊進(jìn)行。 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...
摘要：題目鏈接這道題感覺(jué)是那道的簡(jiǎn)化版，思路都是一樣的。是把所有的點(diǎn)都先放到里面，然后一起遍歷。這種寫法的好處是保證了每個(gè)點(diǎn)都只被放進(jìn)一次，不會(huì)重復(fù)遍歷。保證了時(shí)間復(fù)雜是。可以不寫成層次遍歷的形式，直接，的程序 Walls and Gates 題目鏈接：https://leetcode.com/problems... 這道題感覺(jué)是那道Shortest Distance from All Bu...
摘要：存放過(guò)程中的所有集合為所有的結(jié)尾，則順序存放這個(gè)結(jié)尾對(duì)應(yīng)的中的所有存放同一個(gè)循環(huán)的新加入的，在下一個(gè)循環(huán)再依次對(duì)其中元素進(jìn)行進(jìn)一步的把首個(gè)字符串放入新，再將放入，并將鍵值對(duì)放入，進(jìn)行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...
閱讀 1438·2021-09-22 15:52
閱讀 1493·2019-08-30 15:44
閱讀 906·2019-08-30 14:24
閱讀 2719·2019-08-30 13:06
閱讀 2714·2019-08-26 13:45
閱讀 2797·2019-08-26 13:43
閱讀 1033·2019-08-26 12:01
閱讀 1458·2019-08-26 11:56
