find-best-starting-position

findBestStartingSpot.js

function findBestStartingSpot(matrix) {
  let bestStartingSpot = [];
  let min = Infinity;

  function validMove(row, col, matrixDup) {
    return  row >= 0 &&
            row < matrixDup.length &&
            col >= 0 &&
            col < matrixDup[0].length &&
            matrixDup[row][col] !== '*';
  }

  function bfs(row, col) {
    const queue = [{row, col, count: 0}];
    const results = [];
    const matrixDup = JSON.parse(JSON.stringify(matrix));
  
    while (queue.length) {
      const {row, col, count} = queue.shift();
      if (matrixDup[row][col] === 'x') {
        results.push(count);
      }
      matrixDup[row][col] = '*';
      if (validMove(row+1, col, matrixDup)) queue.push({row: row+1, col, count: count+1});
      if (validMove(row-1, col, matrixDup)) queue.push({row: row-1, col, count: count+1});
      if (validMove(row, col+1, matrixDup)) queue.push({row, col: col+1, count: count+1});
      if (validMove(row+1, col-1, matrixDup)) queue.push({row, col: col-1, count: count+1});
    }
    
    return results.reduce((acc, num) => acc + num);
  }

  for (let row=0; row < matrix.length; row++) {
    for (let col=0; col < matrix[0].length; col++) {
      if (matrix[row][col] === ' ') {
        const count = bfs(row, col);
        if (count < min) {
          min = count;
          bestStartingSpot = [row, col];
        }
      }
    }
  }

  return bestStartingSpot;
}


const grid = [
  [' ', '*', ' '],
  ['x', '*', ' '],
  [' ', 'x', ' '],
  [' ', ' ', '*'],
  [' ', 'x', '*'],
];

console.log(findBestStartingSpot(grid));