Leetcode 286. Walls and Gates(python+cpp)

题目

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.
  

解法1：brutal force(TLE)

从每个位置出发，跟number of islands的方法一样进行BFS寻找最近的gate。但是这个题目跟number of islands不一样的地方在于，可能存在多个可能的路径，而我们要取其中最短的那个。所以对于DFS来说，算法会遍历所有的路径，在这个过程中需要keep track of最短的那个路劲。但是如果用BFS的话，我们并不需要把所有路径找一遍然后选最小的，对于这个问题，lc官方是这么描述的：Since BFS guarantees that we search all rooms of distance d before searching rooms of distance d + 1, the distance to an empty room must be the shortest. 所以这道题目BFS应该会比DFS要快，这边只展示BFS的方法，但这样brutal force的方法依然是超时的

class Solution:def wallsAndGates(self, rooms: List[List[int]]) -> None:"""Do not return anything, modify rooms in-place instead."""def helper(i,j):distance = [[0]*len(rooms[0]) for _ in range(len(rooms))]q = collections.deque()q.append((i,j))dirs = [[0,1],[0,-1],[-1,0],[1,0]]while q:pos = q.popleft()for d in dirs:x = d[0]+pos[0]y = d[1]+pos[1]if x<0 or y<0 or x>=len(rooms) or y>=len(rooms[0]) or rooms[x][y]==-1 or distance[x][y] != 0:continuedistance[x][y] = distance[pos[0]][pos[1]]+1if rooms[x][y] == 0:return distance[x][y]q.append((x,y))return 2147483647if len(rooms) == 0:returnfor i in range(len(rooms)):for j in range(len(rooms[0])):if rooms[i][j] == 2147483647:rooms[i][j] = helper(i,j)

• 时间复杂度：O(m²n²),对于mn个位置，离每个位置最近的gate可能有m*n个位置
• 空间复杂度：O(m*n), 最坏的情况可能需要将所有位置加入队列

解法2：逆向寻找

从gate出发，逆向更新每个位置的值，如果某个位置已经有了数字，比较这个数字的大小和当前步数的值决定是否更新这个位置的最小距离值

class Solution:def wallsAndGates(self, rooms: List[List[int]]) -> None:"""Do not return anything, modify rooms in-place instead."""def helper(i,j,dis):if i<0 or j<0 or i>=len(rooms) or j>=len(rooms[0]) or rooms[i][j]==-1 or rooms[i][j]<dis:returnrooms[i][j] = disdirs = [[0,1],[0,-1],[-1,0],[1,0]]for d in dirs:helper(i+d[0],j+d[1],dis+1)if len(rooms) == 0:return for i in range(len(rooms)):for j in range(len(rooms[0])):if rooms[i][j] == 0:helper(i,j,0)

• 时间复杂度：O(mn)，每个位置寻找gate最多走mn步，但是由于一个位置只访问一次，所以即使有多个门复杂度依旧不变
• 空间复杂度：O(m*n)

C++版本

class Solution {
    
public:void helper(vector<vector<int>>& rooms,int i, int j, int dis){
    int m = rooms.size(), n = rooms[0].size();if(i<0||j<0||i>=m||j>=n||rooms[i][j]==-1||rooms[i][j]<dis) return;rooms[i][j] = dis;helper(rooms,i+1,j,dis+1);helper(rooms,i,j+1,dis+1);helper(rooms,i-1,j,dis+1);helper(rooms,i,j-1,dis+1);}void wallsAndGates(vector<vector<int>>& rooms) {
    if(rooms.size()==0) return;int m = rooms.size(), n = rooms[0].size();for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
    if(rooms[i][j] == 0) helper(rooms,i,j,0);}}}
};