欢迎各位勇者来到力扣城，本次试炼主题为「信物传送」。本次试炼场地设有若干传送带，matrix[i][j] 表示第 i 行 j
列的传送带运作方向，"^","v","<",">" 这四种符号分别表示 上、下、左、右
四个方向。信物会随传送带的方向移动。勇者每一次施法操作，可临时变更一处传送带的方向，在物品经过后传送带恢复原方向。 ![lcp
(2).gif](https://pic.leetcode-cn.com/1649835246-vfupSL-
lcp%20\(2\).gif){:width=300px} 通关信物初始位于坐标 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

Problem: LCP 56. 信物传送

[TOC]

思路

从 T1368 过来，发现这两道题的代码是基本一样的。

解题方法

0-1 BFS 的模板：

先定义好 dist[][] 数组，初始化双端队列，起点入队
每次取队头元素并尝试进行扩展，定义 cost 为从原点到四周顶点的权值，这两题的判断方法都是 若原点的值等于当前扩展的方向则权值为 0 否则为 1 ，然后入队头或队尾
最后返回目标点的 dist 值，或者在第一次弹出目标点时就返回

每个点首次从队头弹出时，当前的 dist 就是最小的，而第一次遇到时不一定最小

复杂度

时间复杂度:
做笔记：每个点最多入队两次出队两次（一次队头一次队尾），故复杂度为 O(mn)
空间复杂度:
O(mn)

Code

本题代码

[]int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
class Solution {
public:
    int conveyorBelt(vector<string>& matrix, vector<int>& start, vector<int>& end) {
        unordered_map<char, int> mp;
        mp['^'] = 1, mp['v'] = 3, mp['<'] = 2, mp['>'] = 0;
        int sx = start[0], sy = start[1], tx = end[0], ty = end[1];
        int m = matrix.size(), n = matrix[0].size();
        int dist[m][n];
        memset(dist, 0x3f, sizeof dist);
        dist[sx][sy] = 0;
        deque<pair<int, int>> q;
        q.push_back({sx, sy});
        while (q.size())
        {
            auto t = q.front();
            q.pop_front();
            int x = t.first, y = t.second;
            //if (x == tx && y == ty) return dist[tx][ty];
            for (int i = 0; i < 4; i++)
            {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < m && b >= 0 && b < n)
                {
                    int cost = (mp[matrix[x][y]] != i);
                    if (dist[x][y] + cost < dist[a][b])
                    {
                        dist[a][b] = dist[x][y] + cost;
                        cost ? q.push_back({a, b}) : q.push_front({a, b});
                    }
                }
            }
        }
        return dist[tx][ty];
    }
};

T1368 代码

[]int dx[5] = {0, 0, 0, 1, -1}, dy[5] = {0, 1, -1, 0, 0}; // 符合本题题意
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int dist[m][n];
        memset(dist, 0x3f, sizeof dist);
        dist[0][0] = 0;
        deque<pair<int, int>> q;
        q.push_back({0, 0});
        while (q.size())
        {
            auto t = q.front();
            q.pop_front();
            int x = t.first, y = t.second;
            for (int i = 1; i <= 4; i++)
            {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < m && b >= 0 && b < n)
                {
                    int cost = (i != grid[x][y]); // 边权 0 1 看这个点的值是否与当前方向相同
                    if (dist[x][y] + cost < dist[a][b]) 
                    {
                        dist[a][b] = dist[x][y] + cost;
                        cost ? q.push_back({a, b}) : q.push_front({a, b});
                    }
                }
            }
        }
        return dist[m - 1][n - 1];
    }
};