Leetcode Maze系列

490 Maze I解析：505. The Maze II解法1：bellman ford解法2：naive Dijkstra解法3：改进版Dijstra总结：follow up阅读

490 Maze I

解析：

这道题目的本质是在一个图上，判断一个节点能否到另一个节点。而节点指的是每个能停下来的位置，而不是路上经过的位置。所以在用BFS的时候，只有能停下来的位置才会被加入到visited数组中去

class Solution: def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool: m,n = len(maze),len(maze[0]) q = collections.deque() q.append((start[0],start[1])) visited = [[False]*n for _ in range(m)] visited[start[0]][start[1]] = True dirs = [[0,1],[1,0],[0,-1],[-1,0]] while q: curr_pos = q.popleft() if curr_pos[0]==destination[0] and curr_pos[1]==destination[1]: return True for d in dirs: x = curr_pos[0]+d[0] y = curr_pos[1]+d[1] while 0<=x<m and 0<=y<n and maze[x][y]==0: x = x+d[0] y = y+d[1] # the visited judgement will only happens here, because only you stopped at a position, then this position is considered as visited. Otherwise if you just pass through a position, we shouldn't mark this position as visited if not visited[x-d[0]][y-d[1]]: q.append((x-d[0],y-d[1])) visited[x-d[0]][y-d[1]] = True return False

C++版本

class Solution { public: bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) { int m = maze.size(), n = maze[0].size(); queue<vector<int>> q; q.push(start); vector<vector<int>> visited(m,vector<int>(n,0)); visited[start[0]][start[1]] = 1; vector<vector<int>> dirs{{0,1},{0,-1},{-1,0},{1,0}}; // bfs int x,y,next_x,next_y; while(!q.empty()){ x = q.front()[0]; y = q.front()[1]; q.pop(); if(x == destination[0] && y == destination[1]){ return true; } for(auto d : dirs){ next_x = x; next_y = y; while(next_x >= 0 && next_x < m && next_y >= 0 && next_y < n && maze[next_x][next_y] == 0){ next_x += d[0]; next_y += d[1]; } next_x -= d[0]; next_y -= d[1]; if(!visited[next_x][next_y]){ q.push({next_x,next_y}); visited[next_x][next_y] = 1; } } } return false; } };

505. The Maze II

解法1：bellman ford

这道题目本质上是个非负边权图找最短路径。节点依旧是每个能够停下来的位置，边权是从上一个能停下来的位置到这个位置走的步数。最简单的实现就是Bellman Ford算法。这个算法其实可以算是一种brutal force，对于从开始节点到某个节点的最短距离的计算，我们需要找到所有可能到达方式里面边权的和最小的路径，对于这道题来说，构建一个distances矩阵，形状与maze相同，并且每个位置的距离初始为一个很大的值。每当到达一个节点的时候，那当前路径的距离和之前这个节点的最短距离比较，如果当前更优，那么更新这个距离，并且将这个点入队，否则不操作，类似贪心的过程

class Solution: def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int: m,n = len(maze),len(maze[0]) q = collections.deque() q.append((start[0],start[1])) distances = [[float('inf')]*n for _ in range(m)] distances[start[0]][start[1]] = 0 dirs = [[0,1],[1,0],[0,-1],[-1,0]] while q: curr_pos = q.popleft() for d in dirs: x = curr_pos[0]+d[0] y = curr_pos[1]+d[1] step = 1 while 0<=x<m and 0<=y<n and maze[x][y]==0: x = x+d[0] y = y+d[1] step += 1 if distances[x-d[0]][y-d[1]]>distances[curr_pos[0]][curr_pos[1]]+step-1: q.append((x-d[0],y-d[1])) distances[x-d[0]][y-d[1]]=distances[curr_pos[0]][curr_pos[1]]+step-1 return distances[destination[0]][destination[1]] if distances[destination[0]][destination[1]]!=float('inf') else -1

C++版本

class Solution { public: int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) { int m = maze.size(), n = maze[0].size(); queue<vector<int>> q; q.push({start[0],start[1],0}); vector<vector<int>> distance(m,vector<int>(n,INT_MAX)); distance[start[0]][start[1]] = 0; vector<vector<int>> dirs{{0,1},{0,-1},{-1,0},{1,0}}; // bfs int x,y,next_x,next_y,step; while(!q.empty()){ x = q.front()[0]; y = q.front()[1]; step = q.front()[2]; q.pop(); for(auto d : dirs){ int tmp_step = step; next_x = x; next_y = y; while(next_x >= 0 && next_x < m && next_y >= 0 && next_y < n && maze[next_x][next_y] == 0){ next_x += d[0]; next_y += d[1]; tmp_step += 1; } next_x -= d[0]; next_y -= d[1]; tmp_step -= 1; if(distance[next_x][next_y] > tmp_step){ q.push({next_x,next_y,tmp_step}); distance[next_x][next_y] = tmp_step; } } } if(distance[destination[0]][destination[1]] != INT_MAX){ return distance[destination[0]][destination[1]]; }else{ return -1; } } };

解法2：naive Dijkstra

naive的Dijkstra实际上是对bellman ford的一种拓展，利用了一种贪心的思想，每次找到距离起点距离最小的位置来进行更新，代码的改动非常小

class Solution: def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int: def find_new_min(): min_pos = [-1,-1] min_val = float('inf') for i in range(m): for j in range(n): if not visited[i][j] and distances[i][j]<min_val: min_pos = [i,j] min_val = distances[i][j] return min_pos m,n = len(maze),len(maze[0]) distances = [[float('inf')]*n for _ in range(m)] distances[start[0]][start[1]] = 0 visited = [[False]*n for _ in range(m)] dirs = [[0,1],[1,0],[0,-1],[-1,0]] while True: curr_pos = find_new_min() if curr_pos[0]<0: break visited[curr_pos[0]][curr_pos[1]] = True for d in dirs: x = curr_pos[0]+d[0] y = curr_pos[1]+d[1] step = 1 while 0<=x<m and 0<=y<n and maze[x][y]==0: x = x+d[0] y = y+d[1] step += 1 if distances[x-d[0]][y-d[1]]>distances[curr_pos[0]][curr_pos[1]]+step-1: distances[x-d[0]][y-d[1]]=distances[curr_pos[0]][curr_pos[1]]+step-1 return distances[destination[0]][destination[1]] if distances[destination[0]][destination[1]]!=float('inf') else -1

解法3：改进版Dijstra

利用heap来储存所有结点的距离，然后每次拓展距离最小的那个节点。这种做法其实只是把bellman ford里面的队列改成了heap

class Solution: def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int: m,n = len(maze),len(maze[0]) distances = [[float('inf')]*n for _ in range(m)] distances[start[0]][start[1]] = 0 dirs = [[0,1],[1,0],[0,-1],[-1,0]] nodes = [(0,start[0],start[1])] while nodes: _,i,j = heapq.heappop(nodes) for d in dirs: x = i+d[0] y = j+d[1] step = 1 while 0<=x<m and 0<=y<n and maze[x][y]==0: x = x+d[0] y = y+d[1] step += 1 if distances[x-d[0]][y-d[1]]>distances[i][j]+step-1: new_d = distances[i][j]+step-1 distances[x-d[0]][y-d[1]]=new_d heapq.heappush(nodes,(new_d,x-d[0],y-d[1])) return distances[destination[0]][destination[1]] if distances[destination[0]][destination[1]]!=float('inf') else -1

总结：

bellman ford和heap版本Dijkstra本质上都不需要visited数组。但是naivi Dijkstra是需要的，原因是在find_min函数里面需要。他们是通过是否能够更新某个节点来进行入队或者push操作的。bellman ford时间复杂度是O(ev)bellman ford每个节点可能会被入队多次，而Dijkstra中每个节点只会被push一次，因为贪心的思想保证了局部最优这两种方法对于有负边权的图也都适用，只不过是算法复杂度的问题heap版本的Dijkstra复杂度是O(e*log(v)),e是边数，v是节点数

follow up阅读

leetcode官方解释里面的Dijkstra Algorithm 详细看看Bellman–Ford algorithm和另一种更优化的最短路径法Shortest Path Faster Algorithm (SPFA)，这是一种队列优化的贝尔曼-福特算法