[LeetCode] 286. 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.

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来解决, 最naive approach就是扫每个点,然后针对每个点用BFS一旦找到0, 代替点的值. 时间复杂度为 O((m*n)^2);
我们还是用BFS的思路, 但是我们先把2D arr 扫一遍, 然后把是0的位置都append进入queue里面, 因为是BFS, 所以每一层最靠近0的位置都会被替换, 并且标记为visited, 然后一直BFS到最后即可.
时间复杂度降为O(m*n)

1. Constraints
1) empty or len(rooms[0]) == 0, edge case
2) size of the rooms < inf
3) 每个元素的值为0, -1,  inf

2. Ideas

BFS     T: O(m*n)    S: O(m*n)

1) edge case,empty or len(rooms[0]) == 0 => return

2) scan 2D arr, 将值为0 的append进入queue里面
3) BFS, 如果是not visited过得, 并且 != 0 or -1, 更改值为dis + 1, 另外append进入queue, add进入visited

3. Code

 class Solution:

     def wallAndGates(self, rooms):

         if not rooms or len(rooms[0]) == 0: return

         queue, lr, lc, visited, dirs = collections.deque(), len(rooms), len(rooms[0]), set(), [(1, 0), (-1, 0), (0, 1), (0, -1)]

         for i in range(lr):

             for j in range(lc):

                 if rooms[i][j] == 0:

                     queue.append((i, j, 0))

                     visited.add((i, j))         while queue:

             pr, pc, dis = queue.popleft()

             for d1, d2 in dirs:

                 nr, nc = pr + d1, pc + d2

                 if 0<= nr < lr and 0<= nc < lc and (nr, nc) not in visited and rooms[nr][nc] != -1:

                     rooms[nr][nc] = dis + 1

                     queue.append((nr,nc, dis + 1))

                     visited.add((nr, nc))

4. Test cases

1) edge case

INF  -1  0  INF

INF INF INF  -1

INF  -1 INF  -1

  0  -1 INF INF

After running function, the 2D grid should be:

  3  -1   0   1

  2   2   1  -1

  1  -1   2  -1

  0  -1   3   4

巴特西

[LeetCode] 286. Walls and Gates_Medium tag: BFS

最新文章

热门文章