let solutionMatrix = [
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0],
];
let N = 4;

let inputMatrix = [
  [2, 1, 0, 0],
  [3, 0, 0, 1],
  [0, 1, 0, 1],
  [0, 1, 0, 1],
];

const solveMaze = (solutionMatrix) => {
  if (solveMazeRun(0, 0) === false) {
    return false;
  } else {
    return solutionMatrix;
  }
};

const solveMazeRun = (i, j) => {
  if (N - 1 == i && N - 1 == j) {
    solutionMatrix[i][j] = 1;
    return true;
  }

  if (isSafeToMove(i, j)) {
    solutionMatrix[i][j] = 1;
    for (let k = 1; k <= inputMatrix[i][j] && k < N; k++) {
      if (solveMazeRun(i + k, j) === true) {
        return true;
      } else if (solveMazeRun(i, j + k) === true) {
        return true;
      }
    }
    solutionMatrix[i][j] = 0;
    return false;
  }
};

const isSafeToMove = (i, j) => {
  if (i < N && j < N && i >= 0 && j >= 0 && inputMatrix[i][j] !== 0)
    return true;
  else return false;
};

console.log(solveMaze(solutionMatrix));