摘要:廣度優先搜索復雜度時間空間思路實際上就是找每個房間到最近的門的距離,我們從每個門開始,廣度優先搜索并記錄層數就行了。這題要注意剪枝,如果下一步是門或者下一步是墻或者下一步已經訪問過了,就不要加入隊列中。
Walls and Gates
廣度優先搜索 復雜度You are given a m x n 2D grid initialized with these three possible values.
-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
For example, given the 2D grid:
INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INFAfter running your function, the 2D grid should be:
3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4
時間 O(NM) 空間 O(N)
思路實際上就是找每個房間到最近的門的距離,我們從每個門開始,廣度優先搜索并記錄層數就行了。如果某個房間之前被標記過距離,那就選擇這個距離和當前距離中較小的那個。這題要注意剪枝,如果下一步是門或者下一步是墻或者下一步已經訪問過了,就不要加入隊列中。否則會超時。
代碼public class Solution { public void wallsAndGates(int[][] rooms) { if(rooms.length == 0) return; for(int i = 0; i < rooms.length; i++){ for(int j = 0; j < rooms[0].length; j++){ // 如果遇到一個門,從門開始廣度優先搜索,標記連通的節點到自己的距離 if(rooms[i][j] == 0) bfs(rooms, i, j); } } } public void bfs(int[][] rooms, int i, int j){ Queuequeue = new LinkedList (); queue.offer(i * rooms[0].length + j); int dist = 0; // 用一個集合記錄已經訪問過的點 Set visited = new HashSet (); visited.add(i * rooms[0].length + j); while(!queue.isEmpty()){ int size = queue.size(); // 記錄深度的搜索 for(int k = 0; k < size; k++){ Integer curr = queue.poll(); int row = curr / rooms[0].length; int col = curr % rooms[0].length; // 選取之前標記的值和當前的距離的較小值 rooms[row][col] = Math.min(rooms[row][col], dist); int up = (row - 1) * rooms[0].length + col; int down = (row + 1) * rooms[0].length + col; int left = row * rooms[0].length + col - 1; int right = row * rooms[0].length + col + 1; if(row > 0 && rooms[row - 1][col] > 0 && !visited.contains(up)){ queue.offer(up); visited.add(up); } if(col > 0 && rooms[row][col - 1] > 0 && !visited.contains(left)){ queue.offer(left); visited.add(left); } if(row < rooms.length - 1 && rooms[row + 1][col] > 0 && !visited.contains(down)){ queue.offer(down); visited.add(down); } if(col < rooms[0].length - 1 && rooms[row][col + 1] > 0 && !visited.contains(right)){ queue.offer(right); visited.add(right); } } dist++; } } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64721.html
摘要:題目鏈接這道題感覺是那道的簡化版,思路都是一樣的。是把所有的點都先放到里面,然后一起遍歷。這種寫法的好處是保證了每個點都只被放進一次,不會重復遍歷。保證了時間復雜是。可以不寫成層次遍歷的形式,直接,的程序 Walls and Gates 題目鏈接:https://leetcode.com/problems... 這道題感覺是那道Shortest Distance from All Bu...
摘要:題目解答每一次加入進來的結點,都時當前位置可到達的最短距離。 題目:You are given a m x n 2D grid initialized with these three possible values. -1 - A wall or an obstacle.0 - A gate.INF - Infinity means an empty room. We use the...
Problem There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it wont stop rolling until hitting a wall. When the ball sto...
閱讀 1569·2021-10-25 09:44
閱讀 2934·2021-09-04 16:48
閱讀 1558·2019-08-30 15:44
閱讀 2502·2019-08-30 15:44
閱讀 1737·2019-08-30 15:44
閱讀 2821·2019-08-30 14:14
閱讀 2971·2019-08-30 13:00
閱讀 2149·2019-08-30 11:09