获取二维数组从右上到下的可能路径

Question

有人能帮我解决这个问题吗？javascript数组表示可遍历的路径和障碍

给定的路线总是成功的，并且不包含交叉口。摩托车总是从0点开始，必须总是到达表的最后一行和最后一列的点，我们不能向左走每个动作对应一个字母：R表示：对，L表示左边，T表示顶部：B代表底部。写下汽车到达目的地必须行驶的路径。

我试过这个代码，但出了问题

var traverse = [
['_','_','X','_','_','_'],
['X','_','X','_','X','_'],
['X','_','_','_','X','_'],
['X','X','X','X','X','_'],
];
// Prints "0: a, 1: b, 2: c"
var current, next, last, itinerary, column ;
traverse.forEach(function callback(value, index) {
// console.log(`${index}: ${value}`);
console.log(value);
current = value[index];
next = value[index];
if (index > 0) {
last = current[index - 1];
}
addDirection(current, column, 'D', itinerary);
addDirection(next, column, 'B', itinerary);
addDirection(last, column, 'H', itinerary);
column++;

});
function addDirection(line, column, direction, itinerary)
{
line.forEach(function callback(value, index) {
if(index == column){
if (line[column] == '_') {
itinerary.push(direction);
}
}
});
}
console.log(itinerary);

在本例中，行程必须包含R/B/B/R/T/R/B/B/B/B

Answer 1

许多问题中的一些：

• 您的算法从上到下访问矩阵的行，因此它永远无法找到向上移动的路径
• 变量column从不初始化
• 变量current从单元格中获取值，但在addDirection中，它被视为一行。line.forEach调用永远无法工作

算法无法工作。我会在矩阵中进行搜索，在矩阵中检查所有三个动作(除了从我们来的地方返回的那一个)，如果可能的话，就会进行。如果它导致了一个死胡同，回溯应该发生。这基本上是对矩阵中_字段的深度优先遍历：

function getPath(matrix, row=0, col=0, vertical=0) {
if (matrix[row]?.[col] != "_") return null; // Obstacle
if (row == matrix.length - 1 && col == matrix[0].length - 1) return []; // Found target
if (vertical != -1) {
const path = getPath(matrix, row + 1, col, 1);
if (path) return ["B", ...path];
}
if (vertical != 1) {
const path = getPath(matrix, row - 1, col, -1);
if (path) return ["T", ...path];
}
const path = getPath(matrix, row, col + 1, 0);
if (path) return ["R", ...path];
return null;
}
const traverse = [
['_','_','X','_','_','_'],
['X','_','X','_','X','_'],
['X','_','_','_','X','_'],
['X','X','X','X','X','_'],
];
const itinerary = getPath(traverse);
console.log(...itinerary);

我不确定矩阵是否会有死胡同，比如这个：

const traverse = [
['_','_','X','_','_','_'],
['X','_','X','_','X','_'],
['X','_','_','_','X','_'],
['X','_','X','X','X','_'],
];

(请注意底部一行中多余的"_")。回溯算法将确保，如果它首先朝着错误的方向前进，遇到死胡同，它会回溯，然后仍然尝试另一个方向。如果这样的输入是不可能的，那么回溯算法就有点过头了，但它实际上并不代表太多代码，所以这样做也没什么坏处。

Answer 2

let traverse = [
['_', '_', 'X', '_', '_', '_'],
['X', '_', 'X', '_', 'X', '_'],
['X', '_', '_', '_', 'X', '_'],
['X', 'X', 'X', 'X', 'X', '_'],
];
let currentX = 0, currentY = 0;
let itinerary = [];
let lastDirection = '';
while(currentX != traverse[0].length - 1 && currentY != traverse.length - 1) {
if (lastDirection !== 'L' && traverse[currentY][currentX + 1] === '_') {
addDirection('R');
currentX++;
} else if (lastDirection !== 'T' && traverse[currentY + 1][currentX] === '_') {
addDirection('B');
currentY++;
} else if (lastDirection !== 'R' && traverse[currentY][currentX - 1] === '_') {
addDirection('L');
currentX--;
} else if (lastDirection !== 'B' && traverse[currentY - 1][currentX] === '_') {
addDirection('T');
currentY--;
}
}
console.log(itinerary.join('/'));
function addDirection(dir) {
itinerary.push(dir);
lastDirection = dir;
}