美文网首页
286. Walls and Gates

286. Walls and Gates

作者: 我是你的果果呀 | 来源:发表于2016-12-10 11:56 被阅读0次

    You are given am x n2D 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 value231- 1 = 2147483647to representINFas you may assume that the distance to a gate is less than2147483647.
    Fill each empty room with the distance to itsnearestgate. If it is impossible to reach a gate, it should be filled withINF.
    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

    BFS, 把0 一起都放到队列里, 然后开始循化队列,如果 队列里面的数字旁边遇到INF, 则 把INF的值更改为队列值+1, 再把这个被更新的INF放到队列里面。

    相关文章

      网友评论

          本文标题:286. Walls and Gates

          本文链接:https://www.haomeiwen.com/subject/ihaymttx.html