LCP 56. 信物传送

说在前面

🎈每天进行一道算法题目练习，今天的题目是“LCP 56. 信物传送”，让我们一起来温习一下寻路算法。

问题描述

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

本次试炼场地设有若干传送带，matrixi 表示第 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

思路分析

这是一道地图的寻路问题，对于这种问题我们可以使用dfs（深度优先搜索算法）和bfs（广度优先搜索算法）来进行解题。本题中我使用了记忆化的dfs深度优先搜索算法来进行解题。\
题目的意思是地图的每一块地方都有一个传送带，我们可以顺着传送带去到下一个方块，并且我们可以改变传送带的方向，现在要我们计算从起点到终点，我们需要修改传送带方向的数量。\

定义遍历的四个方向

首先需要设定遍历的方向

let dx = [0, 1, 0, -1],
    dy = [1, 0, -1, 0];

记录到达当前位置的最小步数

需要记录到达每一个方块最小步数，当遍历到比当前需要的步数还多时，我们就不需要继续往下遍历了。

let flag = new Array(matrix.length);
for (let i = 0; i < flag.length; i++) {
    flag[i] = new Array(matrix[0].length).fill(Infinity);
}

flag[x][y] = Math.min(flag[x][y], step);

if (flag[x][y] <= step) {
  return;
}

判断是否需要改变方向

当前遍历的方向与传送带的方向不一致时，需要改变传送带方向。

let judge = function (str, i) {
    if (i == 0 && str == ">") return 0;
    if (i == 1 && str == "v") return 0;
    if (i == 2 && str == "<") return 0;
    if (i == 3 && str == "^") return 0;
    return 1;
};

到达终点时更新最少步数

if (x == end[0] && y == end[1]) {
  res = Math.min(res, step);
  return;
}

AC代码

/**
 * @param {string[]} matrix
 * @param {number[]} start
 * @param {number[]} end
 * @return {number}
 */
var conveyorBelt = function (matrix, start, end) {
  let dx = [0, 1, 0, -1],
    dy = [1, 0, -1, 0];
  let flag = new Array(matrix.length);
  for (let i = 0; i < flag.length; i++) {
    flag[i] = new Array(matrix[0].length).fill(Infinity);
  }
  let res = Infinity;
  let judge = function (str, i) {
    if (i == 0 && str == ">") return 0;
    if (i == 1 && str == "v") return 0;
    if (i == 2 && str == "<") return 0;
    if (i == 3 && str == "^") return 0;
    return 1;
  };
  let dfs = function (x, y, step) {
    if (
      x < 0 ||
      y < 0 ||
      x >= matrix.length ||
      y >= matrix[0].length ||
      res == 0 ||
      flag[x][y] <= step
    ) {
      return;
    }
    if (x == end[0] && y == end[1]) {
      res = Math.min(res, step);
      return;
    }
    for (let i = 0; i < 4; i++) {
      if (res == 0) return;
      let j = judge(matrix[x][y], i);
      flag[x][y] = Math.min(flag[x][y], step);
      dfs(x + dx[i], y + dy[i], step + j);
      if (res == 0) return;
    }
  };
  dfs(start[0], start[1], 0);
  return res;
};

说在后面

🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。