¿Alguien puede ayudarme a resolver este problema? Una matriz de javascript representa un camino transitable y obstáculos
La ruta dada siempre es exitosa y no contiene una intersección. Una moto siempre partirá del punto 0 y siempre debe llegar al punto de la última línea y última columna de la tabla y no podemos ir a la izquierda A cada movimiento le corresponde una letra: R para: derecha, L para izquierda, T para arriba: B para Inferior. Escribe el camino que debe recorrer el automóvil para llegar a su meta.
Probé con este código pero algo anda mal
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);En este ejemplo, el itinerario debe contener R/B/B/R/R/T/T/R/R/B/B/B
Algunos de los muchos problemas:
column variable nunca se inicializa.current obtiene un valor de una celda, pero en addDirection se trata como una línea. La llamada line.forEach nunca puede funcionar. El algoritmo no puede funcionar. Yo usaría una búsqueda en la matriz donde se inspeccionan los tres movimientos (excepto el que va de donde vinimos) y si es posible, se hace. Si conduce a un callejón sin salida, debe ocurrir un retroceso. Esto es básicamente un recorrido primero en profundidad sobre los campos _ en la matriz:
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);No estaba seguro de si la matriz podría tener callejones sin salida, como este:
const traverse = [ ['_','_','X','_','_','_'], ['X','_','X','_','X','_'], ['X','_','_','_','X','_'], ['X','_','X','X','X','_'], ];(Observe el "_" adicional en la fila inferior). El algoritmo de retroceso se asegurará de que si primero va en la dirección incorrecta y se encuentra con un callejón sin salida, retrocederá y aún intentará en la otra dirección. Si tal entrada no es posible, entonces el algoritmo de retroceso es un poco exagerado, pero en realidad no representa mucho código, por lo que no está de más hacerlo de esta manera.
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; }