成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

286. Walls and Gates

megatron / 2302人閱讀

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

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

解答：
每一次加入進來的結(jié)點，都時當(dāng)前位置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});
        }
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64915.html

相關(guān)文章

  • [Leetcode] Walls and Gates 墻與門

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

    Edison 評論0 收藏0

  • Walls and Gates

    摘要：題目鏈接這道題感覺是那道的簡化版，思路都是一樣的。是把所有的點都先放到里面，然后一起遍歷。這種寫法的好處是保證了每個點都只被放進一次，不會重復(fù)遍歷。保證了時間復(fù)雜是?？梢圆粚懗蓪哟伪闅v的形式，直接，的程序 Walls and Gates 題目鏈接：https://leetcode.com/problems... 這道題感覺是那道Shortest Distance from All Bu...

    CKJOKER 評論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 評論0 收藏0

  • 用并查集(find-union)實現(xiàn)迷宮算法以及最短路徑求解

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

    xiangchaobin 評論0 收藏0

  • 【mongoDB基礎(chǔ)篇①】安裝與常用操作語句

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

    UCloud 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<