Leetcode 1293. Shortest Path in a Grid with Obstacles Elimination (python+cpp)_综合

题目

在这里插入图片描述

解法：BFS

首先是个最短路径问题，所以很自然的想到要用BFS。唯一特殊的是，这边的visited数组比较特殊，某个位置是否被访问过不仅仅取决于位置本身，还取决于到达这个位置时剩下的k值，想清楚这点。然后关于k在哪里进行修改既可以在访问每一个位置时，也可以在向四个方向进行搜索时，下面两种解法都提供一下

版本一

class Solution:def shortestPath(self, grid: List[List[int]], k: int) -> int:m = len(grid)n = len(grid[0])q = collections.deque()visited = [[False]*n for _ in range(m)]q.append((0,0,k,0))visited = {
    }visited[(0,0,k)] = Truedirs = [[0,1],[0,-1],[-1,0],[1,0]]while q:i,j,curr_k,step = q.popleft()if i==m-1 and j==n-1:return stepif grid[i][j] == 1:if curr_k>0:curr_k -= 1else:continue for d in dirs:x = i+d[0]y = j+d[1]if 0<=x<m and 0<=y<n and (x,y,curr_k) not in visited:q.append((x,y,curr_k,step+1))visited[(x,y,curr_k)] = Truereturn -1

版本二

class Solution:def shortestPath(self, grid: List[List[int]], k: int) -> int:m = len(grid)n = len(grid[0])q = collections.deque()visited = [[False]*n for _ in range(m)]q.append((0,0,k,0))visited = {
    }visited[(0,0,k)] = Truedirs = [[0,1],[0,-1],[-1,0],[1,0]]while q:i,j,curr_k,step = q.popleft()if i==m-1 and j==n-1:return stepfor d in dirs:x = i+d[0]y = j+d[1]if 0<=x<m and 0<=y<n:if grid[x][y] == 1:if curr_k>0 and (x,y,curr_k-1) not in visited:q.append((x,y,curr_k-1,step+1))visited[(x,y,curr_k-1)] = Trueelse:if (x,y,curr_k) not in visited:q.append((x,y,curr_k,step+1))visited[(x,y,curr_k)] = Truereturn -1

C++版本：
visited数组在python解法里是直接用字典实现的，因为python不是很方便定义三维数组。但是在C++里面就可以很轻松的定义三维数组

class Solution {
    
public:int shortestPath(vector<vector<int>>& grid, int k) {
    int m = grid.size(), n = grid[0].size();queue<vector<int>> q;q.push({
    0,0,k,0});vector<vector<vector<int>>> visited(m,vector<vector<int>>(n,vector<int>(k+1,0)));visited[0][0][k] = 1;vector<pair<int,int>> dirs{
    {
    0,1},{
    0,-1},{
    -1,0},{
    1,0}};while (!q.empty()){
    int i = q.front()[0];int j = q.front()[1];int curr_k = q.front()[2];int step = q.front()[3];q.pop();if (i==m-1 && j==n-1) return step;if (grid[i][j] == 1){
    if (curr_k>0){
    curr_k -= 1;}else{
    continue;}}for (auto d:dirs){
    int x = i+d.first;int y = j+d.second;if (x>=0 && x<m && y>=0 && y<n && visited[x][y][curr_k]!=1){
    q.push({
    x,y,curr_k,step+1});visited[x][y][curr_k] = 1;}}}return -1;}
};

版本2

class Solution {
    
public:int shortestPath(vector<vector<int>>& grid, int k) {
    int m = grid.size(), n = grid[0].size();queue<vector<int>> q;q.push({
    0,0,k,0});vector<vector<vector<int>>> visited(m,vector<vector<int>>(n,vector<int>(k+1,0)));visited[0][0][k] = 1;vector<pair<int,int>> dirs{
    {
    1,0},{
    -1,0},{
    0,1},{
    0,-1}};// start bfsint x, y, next_x, next_y, step, curr_k;while(!q.empty()){
    x = q.front()[0];y = q.front()[1];curr_k = q.front()[2];step = q.front()[3];q.pop();if(x == m-1 && y == n-1){
    return step;}for(auto d : dirs){
    next_x = x + d.first;next_y = y + d.second;if(next_x >= 0 && next_x < m && next_y >= 0 && next_y < n){
    if(grid[next_x][next_y] == 1){
    if(curr_k > 0 && visited[next_x][next_y][curr_k-1] == 0){
    q.push({
    next_x,next_y,curr_k-1,step+1});visited[next_x][next_y][curr_k-1] = 1;}}else{
    if(visited[next_x][next_y][curr_k] == 0){
    q.push({
    next_x,next_y,curr_k,step+1});visited[next_x][next_y][curr_k] = 1;}}}}}return -1;}
};

二刷

二刷一开始的时候还是用dijkstra来做的，结果tle了

class Solution {
    
public:int shortestPath(vector<vector<int>>& grid, int k) {
    int m = grid.size(), n = grid[0].size();vector<vector<vector<int>>> dists(m,vector<vector<int>>(n,vector<int>(k+1,INT_MAX)));priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;pq.push({
    0,0,0,0});dists[0][0][0] = 0;vector<vector<int>> dirs{
    {
    0,1},{
    0,-1},{
    1,0},{
    -1,0}};while(!pq.empty()){
    auto curr = pq.top();pq.pop();int curr_dist = curr[0], i = curr[1], j = curr[2], curr_remove = curr[3];for(auto& d : dirs){
    int x = i + d[0];int y = j + d[1];if(x < 0 || y < 0 || x >= m || y >= n) continue;if(grid[x][y] == 0){
    if(curr_dist + 1 < dists[x][y][curr_remove]){
    dists[x][y][curr_remove] = curr_dist + 1;// dists[x][y][1] = curr_remove;pq.push({
    curr_dist+1,x,y,curr_remove});}}else{
    if(curr_remove <= k-1 && curr_dist+1 < dists[x][y][curr_remove+1]){
    dists[x][y][curr_remove+1] = curr_dist + 1;pq.push({
    curr_dist+1,x,y,curr_remove+1});}}}}int ans = INT_MAX;for(auto it : dists[m-1][n-1]){
    ans = min(ans,it);}return ans == INT_MAX ? -1 : ans;;}
};

但是这边实际上是不需要dijkstra的，为什么呢？两个问题：

对于这道题，实际上是个起点终点固定，以及边权都相等的图里面找最短路径。当每条边都一样长的时候，那么走了多少步距离就是多少。所以如果用bfs来做的话，第一次碰到终点的时候一定就是距离最短的。而对于边权重不一样的情况，相同的步数并不代表距离相同，从而也不能保证在dfs中第一次碰到某个节点就是最短的情况。所以对于这边，并不需要maintain一个数组来记录距离，通过距离大小来判断是否入队列这种操作，而只需visited数组即可
这道题的特殊处在于，还有另一个纬度是k，所以对于某一个位置，虽然在k固定的情况下，从起点到当前位置的最短距离一定是第一次碰到，但是k在变化，所以需要增加一个纬度来代表是否访问过这个状态。比如到某个位置的时候，可能当前的步数比之前的要大，但是用掉的remove可能更小，所以到最终的目的地的距离到底是哪条路径更大其实并不能确定，所以两种可能性都需要访问

总结来说，当边的权重固定的时候，直接bfs就可以做，虽然dijkstra也能做，但是时间复杂度一般会更高