[leetcode]

admin管理员组

文章数量:1794759

[leetcode]

题目

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

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

解题思路

递归 + 剪枝 + 缓存；

• 从开始上下左右移动
• 数组缓存移动到当前位置所需要的最小值
• 移动到当前位置需要施法的次数大于此位置数组缓存值，终止递归
• 设置递归边界

代码

var conveyorBelt = function (matrix, start, end) {const m = matrix.length;const n = matrix[0].length;// 每一步都需要施法，最大施法步数const max = Math.abs(start[0] - end[0]) + Math.abs(start[1] - end[1]);const list = [];for (let i = 0; i < m; i++) {list[i] = [];for (let j = 0; j < n; j++) {list[i][j] = max;}}const row = [0, 0, 1, -1];const col = [-1, 1, 0, 0];dfs(start[0], start[1], 0);// 返回答案const [x, y] = end;return list[x][y];function dfs(i, j, l) {if (i < 0 || j < 0 || i >= m || j >= n) return;// 剪枝的核心if (list[i][j] <= l) return;list[i][j] = Math.min(list[i][j], l);if (i === end[0] && j === end[1]) {return;}if (matrix[i][j] === '<') {dfs(i, j - 1, l);}if (matrix[i][j] === '>') {dfs(i, j + 1, l);}if (matrix[i][j] === '^') {dfs(i - 1, j, l);}if (matrix[i][j] === 'v') {dfs(i + 1, j, l);}for (let k = 0; k < 4; k++) {const x = row[k] + i;const y = col[k] + j;if (x >= 0 && x < m && y >= 0 && y < n) {dfs(x, y, l + 1);}}}
}; 

本文标签： LeetCode