286. Walls and Gates

megatron 發布于2019-08-14 14:16 / 2293人閱讀

摘要：題目解答每一次加入進來的結點，都時當前位置可到達的最短距離。

題目：
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 INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

解答：
每一次加入進來的結點，都時當前位置gate可到達的最短距離。用BFS逐層掃。

public void wallsAndGates(int[][] rooms) {
    if (rooms == null || rooms.length == 0 || rooms[0].length == 0) return;
    Queue q = new LinkedList<>();
    int m = rooms.length, n = rooms[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (rooms[i][j] == 0) {
                q.add(new int[]{i, j});
            }
        }
    }
    
    int[][] dir = {{-1, 0},{1, 0},{0, 1},{0, -1}};
    while (!q.isEmpty()) {
        int[] curt = q.poll();
        int i = curt[0], j = curt[1];
        for (int k = 0; k < dir.length; k++) {
            int x = i + dir[k][0], y = j + dir[k][1];
            if (x < 0 || x > m - 1 || y < 0 || y > n - 1 || rooms[x][y] != Integer.MAX_VALUE) {
                continue;
            }
            rooms[x][y] = rooms[i][j] + 1;
            q.add(new int[] {x, y});
        }
    }
}

GPU云服務器云服務器 Walls Gates And between and

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

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

[Leetcode] Walls and Gates 墻與門

摘要：廣度優先搜索復雜度時間空間思路實際上就是找每個房間到最近的門的距離，我們從每個門開始，廣度優先搜索并記錄層數就行了。這題要注意剪枝，如果下一步是門或者下一步是墻或者下一步已經訪問過了，就不要加入隊列中。 Walls and Gates You are given a m x n 2D grid initialized with these three possible values....

Edison 2019-08-14 12:48 評論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] 490. The Maze (BFS/DFS)

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

smartlion 2019-08-16 13:51 評論0 收藏0
用并查集(find-union)實現迷宮算法以及最短路徑求解

摘要：本人郵箱歡迎轉載轉載請注明網址代碼已經全部托管有需要的同學自行下載引言迷宮對于大家都不會陌生那么迷宮是怎么生成已經迷宮要如何找到正確的路徑呢用代碼又怎么實現帶著這些問題我們繼續往下看并查集朋友圈有一種算法就做并查集什么意思呢比如現在有零本人郵箱: 歡迎轉載,轉載請注明網址 http://blog.csdn.net/tianshi_kcogithub: https://github.c...

xiangchaobin 2019-08-16 10:30 評論0 收藏0
【mongoDB基礎篇①】安裝與常用操作語句

摘要：簡述與同為數據庫但是為數據庫而為文檔型數據庫存儲的是文檔的二進制化內部執行引擎為解釋器把文檔存儲成結構在查詢時轉換為對象并可以通過熟悉的語法來操作的安裝啟動在上直接下載解壓運行即可本身是已編譯好的二進制可執行文件如果報錯說明你的服務器和簡述 mongoDB與redis同為noSql數據庫,但是redis為kv數據庫(key/value),而mongoDB為文檔型數據庫存儲的是文檔(B...

UCloud 2019-06-26 16:58 評論0 收藏0