Skip to content

Latest commit

 

History

History
128 lines (99 loc) · 3.67 KB

0286._Walls_and_Gates.md

File metadata and controls

128 lines (99 loc) · 3.67 KB

286. Walls and Gates

难度: Medium

刷题内容

原题连接

内容描述

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

解题方案

思路 1 - 时间复杂度: O(N^4)- 空间复杂度: O(N^2)******

定义一个dfs函数的返回值是当前点目前的距离gate的最短距离

然后思路是对于每一个点往外dfs走，不停更新rooms，结果超时间，最后一个case没过

class Solution:
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        """
        row = len(rooms)
        col = len(rooms[0]) if row else 0
        nexts = [[0,1], [0,-1], [1,0], [-1,0]]
        
        def dfs(i, j, visited):
            # print(i, j)
            if (i, j) in visited:
                return rooms[i][j]
            visited.add((i,j))
            if not (0 <= i < row and 0 <= j < col):
                return -1
            if rooms[i][j] == -1 or rooms[i][j] == 0:
                return rooms[i][j]
            res = rooms[i][j]
            for nxt in nexts:
                tmp = dfs(i + nxt[0], j + nxt[1], visited)
                res = min(res, tmp + 1 if tmp > -1 else 2 ** 31 - 1)
            if res != rooms[i][j]:
                rooms[i][j] = res
            # print(i,j,res)
            # print()
            return res
        for i in range(row):
            for j in range(col):
                dfs(i, j, set())

思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******

后面想到可以从每一个gate往外bfs, 然后不停更新最短距离

If you are having difficulty to derive the time complexity, start simple.

Let us start with the case with only one gate. 
The breadth-first search takes at most n^2 steps to reach all rooms, 
therefore the time complexity is O(N^2). 
But what if you are doing breadth-first search from k gates?

Once we set a room's distance, 
we are basically marking it as visited, which means each room is visited at most once. 
Therefore, the time complexity does not depend on the number of gates and is O(N^2).

class Solution:
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        """
        row = len(rooms)
        col = len(rooms[0]) if row else 0
        nexts = [[0,1], [0,-1], [1,0], [-1,0]]
        
        def bfs(i, j):
            queue = [(i,j)]
            while queue:
                x, y = queue.pop()
                for nxt in nexts:
                    if not (0 <= x + nxt[0] < row and 0 <= y + nxt[1] < col):
                        continue
                    if rooms[x+nxt[0]][y+nxt[1]] > rooms[x][y] + 1:
                        rooms[x+nxt[0]][y+nxt[1]] = rooms[x][y] + 1
                        queue.append((x+nxt[0], y+nxt[1]))
                        
        for i in range(row):
            for j in range(col):
                if rooms[i][j] == 0:
                    bfs(i, j)