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.
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]; Dequequeue = 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; } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/72256.html
摘要:從第一個點出發(fā)表示空地,表示已經(jīng)走過的空地,避免重復。看起來就像一層層的涂色。 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 ...
摘要:如果該沒有被之前所有的訪問過,就不可能成為答案根據(jù)要求的位置能到所有的,其他與它相鄰的點也是這樣。和用矩陣比,縮小了每次遍歷的范圍。 Shortest Distance from All Buildings 題目鏈接:https://leetcode.com/problems... 這道題要求最短的距離,一般這種要求可以到的地方的距離,都需要把整個圖遍歷一遍,遍歷一般就是bfs和dfs...
摘要:存放過程中的所有集合為所有的結(jié)尾,則順序存放這個結(jié)尾對應(yīng)的中的所有存放同一個循環(huán)的新加入的,在下一個循環(huán)再依次對其中元素進行進一步的把首個字符串放入新,再將放入,并將鍵值對放入,進行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...
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...
摘要:代碼第一次寫入就先不比較第一次寫入就先不比較哈希表法復雜度時間空間思路因為會多次調(diào)用,我們不能每次調(diào)用的時候再把這兩個單詞的下標找出來。我們可以用一個哈希表,在傳入字符串數(shù)組時,就把每個單詞的下標找出存入表中。 Shortest Word Distance Given a list of words and two words word1 and word2, return the ...
閱讀 1893·2021-11-22 15:25
閱讀 1250·2021-11-19 09:40
閱讀 1857·2021-09-27 13:57
閱讀 986·2021-09-22 15:10
閱讀 972·2021-08-16 11:01
閱讀 2971·2021-07-23 17:51
閱讀 765·2019-08-30 15:55
閱讀 818·2019-08-30 13:58