rat-in-maze.ts

export function ratInAMaze(maze: Array<Array<number>>) {
  const solution: Array<Array<number>> = [];

  for (let i = 0; i < maze.length; i++) {
    solution[i] = [];
    for (let j = 0; j < maze[i].length; j++) {
      solution[i][j] = 0;
    }
  }

  if (findPath(maze, 0, 0, solution) === false) {
    return solution;
  } else {
    return 'NO PATH FOUND';
  }
}

function findPath(
  maze: Array<Array<number>>,
  x: number,
  y: number,
  solution: Array<Array<number>>
) {
  const n = maze.length;
  // check if maze[x][y] is feasible to move
  if (x === n - 1 && y === n - 1) {
    // we have reached
    solution[x][y] = 1;
    return true;
  }

  // Check if maze[x][y] is valid
  if (isSafe(maze, x, y) === true) {
    // mark x,y as part of solution path
    solution[x][y] = 1;

    /* Move forward in x direction */
    if (findPath(maze, x + 1, y, solution)) {
      return true;
    }

    /* If moving in x direction doesn't give
       solution then  Move down in y direction */
    if (findPath(maze, x, y + 1, solution)) {
      return true;
    }

    /* If none of the above movements work then
       BACKTRACK: unmark x,y as part of solution
       path */
    solution[x][y] = 0;
    return false;
  }

  return false;
}

function isSafe(maze: Array<Array<number>>, x: number, y: number) {
  const n = maze.length;
  // check if x and y are in limits and cell is not blocked
  if (x >= 0 && y >= 0 && x < n && y < n && maze[x][y] !== 0) {
    return true;
  }
  return false;
}