Can someone help me solve this problem? A javascript array represents a traversable path and obstacles

The route given is always sucess and does not contain an intersection. A motorcycle will always start from point 0 and must always reach the point of the last line and last column of the table and we cant go left A letter corresponds to each movement: R for: right, L for left, T for top: B for Bottom. Write down the path the car must travel to reach its goal.

I tried with this code but something is wrong

    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);
    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);

In this exemple the itinerary must contain R/B/B/R/R/T/T/R/R/B/B/B

CodePudding user response：

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;
}

CodePudding user response：

Some of the many issues:

• Your algorithm visits the rows of the matrix from top to bottom, so it will never be able to find a path that moves back upwards.
• The variable column is never initialised
• The variable current gets a value from a cell, but in addDirection it is treated as a line. The line.forEach call can never work.

The algorithm cannot work. I would use a search in the matrix where all three moves are inspected (except the one that goes back from where we came) and if it is possible, it is made. If it leads to a dead-end, backtracking should occur. This is basically a depth-first traversal over the _ fields in the matrix:

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);

I was not sure whether the matrix could have dead-ends, like this one:

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

(Notice the extra "_" in the bottom row). The backtracking algorithm will make sure that if it goes in the wrong direction first, meeting a dead end, it will backtrack and still try the other direction. If such input is not possible, then the backtracking algorithm is a bit of overkill, but it actually does not represent much code, so it doesn't hurt to do it this way.