LeetCode 2022春季赛 2. 信物传送（迪杰斯特拉-最短路径）

• • 1. 题目
  • 2. 解题

欢迎各位勇者来到力扣城，本次试炼主题为「信物传送」。

本次试炼场地设有若干传送带，matrix[i][j] 表示第 i 行 j 列的传送带运作方向，"^","v","<",">" 这四种符号分别表示 上、下、左、右 四个方向。
信物会随传送带的方向移动。勇者每一次施法操作，可临时变更一处传送带的方向，在物品经过后传送带恢复原方向。

通关信物初始位于坐标 start处，勇者需要将其移动到坐标 end 处，请返回勇者施法操作的最少次数。

注意：
start 和 end 的格式均为 [i,j]

示例 1:
输入：matrix = [">>v","v^<","<><"], 
start = [0,1], end = [2,0]
输出：1
解释：
如上图所示
当信物移动到 [1,1] 时，勇者施法一次将 [1,1] 的传送方向 ^ 从变更为 <
从而信物移动到 [1,0]，后续到达 end 位置
因此勇者最少需要施法操作 1 次

示例 2:
输入：matrix = [">>v",">>v","^<<"], 
start = [0,0], end = [1,1]
输出：0
解释：勇者无需施法，信物将自动传送至 end 位置

示例 3:
输入：matrix = [">^^>","<^v>","^v^<"], 
start = [0,0], end = [1,3]
输出：3

提示：
matrix 中仅包含 '^'、'v'、'<'、'>'
0 < matrix.length <= 100
0 < matrix[i].length <= 100
0 <= start[0],end[0] < matrix.length
0 <= start[1],end[1] < matrix[i].length

https://leetcode-cn.com/contest/season/2022-spring/problems/6UEx57/

• 迪杰斯特拉，最短路径

typedef pair pii;
struct cmp{
    bool operator()(pii& a, pii& b) const
    {
        return a.first > b.first;
    }
};
class Solution {
    vector> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    int conveyorBelt(vector& matrix, vector& start, vector& end) {
        int m = matrix.size(), n = matrix[0].size();
        vector> mindis(m, vector(n, INT_MAX));
        priority_queue, cmp> q;
        q.push({0, start[0]*128+start[1]}); 
        // 存储到该点的最小施法次数，压缩的位置信息
        mindis[start[0]][start[1]] = 0;
        while(!q.empty())
        {
            auto tp = q.top();
            q.pop();
            int time = tp.first, x = tp.second/128, y = tp.second%128;
            if(x==end[0] && y==end[1])
                return time;
            for(int i = 0; i < 4; ++i)
            {
                int nx = x+dir[i][0], ny = y+dir[i][1];
                if(nx>=0 && nx=0 && ny
                    if((matrix[x][y]=='^' && i==0) || (matrix[x][y]=='v' && i==1) || 
                      (matrix[x][y]=='<' && i==2) || (matrix[x][y]=='>' && i==3))
                    { // 不施法就能走过来，且是更优的走法
                        if(time < mindis[nx][ny])
                        {
                            q.push({time, nx*128+ny});
                            mindis[nx][ny] = time;
                        }
                    }
                    else
                    {  // 需要施法才能走过来，且是更优的走法，次数+1 
                        if(time+1 < mindis[nx][ny])
                        {
                            q.push({time+1, nx*128+ny});
                            mindis[nx][ny] = time+1;
                        }
                    }
                }
            }
        }
        return -1;
    }
};

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！