Rat in a maze

Imagine a rat trapped in a maze represented by an N x N grid. Each cell in the grid is either: open represented by the value 1 allowing the rat to move through, or blocked represented by the value 0 preventing the rat from entering. The rat starts at the top-left corner (0, 0) and aims to reach the bottom-right corner (N-1, N-1). Determine all possible paths the rat can take to reach the destination. The rat can move in four directions: Up (U), Down (D), Left (L) and Right (R). Return a list of all possible paths, represented as strings of directions (e.g., "DDRLRRUUDD"). The paths should be sorted in lexicographical order.

Hint

The "rat" (representing the algorithm) begins its journey at the top-left corner of the maze. From its current position, the rat checks all possible directions it can move (up, down, left, right). It ensures each move stays within the maze boundaries and doesn't lead into a blocked area. If a move is valid, the rat "takes" that path and continues exploring deeper into the maze. If a chosen path doesn't lead to the destination, the rat "backtracks." This means it undoes the last move it made and tries a different direction.

• Python
• Javascript
•  Run

maze = [
  [1, 0, 0, 0],
  [1, 1, 0, 1],
  [1, 1, 0, 0],
  [0, 1, 1, 1]
]

directions = {
  "U": [-1, 0],
  "D": [1, 0],
  "L": [0, -1],
  "R": [0, 1],
}

def valid(maze, x, y):
  n = len(maze)
  return x >= 0 and x < n and y >= 0 and y < n and maze[x][y] == 1

def move(maze, x, y, path, out):
  n = len(maze)

  if x == n - 1 and y == n - 1:
    out.append(path)

  maze[x][y] = 0

  for d in directions:
    next_x = x + directions[d][0]
    next_y = y + directions[d][1]

    if valid(maze, next_x, next_y):

      path += d
      move(maze, next_x, next_y, path, out)
      path = path[:-1]

  maze[x][y] = 1

output = []

move(maze, 0, 0, "", output)

print(output)

const maze = [
  [1, 0, 0, 0],
  [1, 1, 0, 1],
  [1, 1, 0, 0],
  [0, 1, 1, 1]
];

const directions = {
  U: [-1, 0],
  D: [1, 0],
  L: [0, -1],
  R: [0, 1],
}

function valid(maze, x, y) {
  const n = maze.length;
  return x >= 0 && y >= 0 && x < n && y < n && maze[x][y] === 1;
}

function move(maze, x, y, path, out) {
  const n = maze.length;

  if (x === n - 1 && y === n - 1) {
    out.push(path);
    return;
  }

  maze[x][y] = 0;

  for (const d in directions) {
    const next_x = x + directions[d][0];
    const next_y = y + directions[d][1];

    if (valid(maze, next_x, next_y)) {
      path += d;
      move(maze, next_x, next_y, path, out);
      path = path.slice(0, -1);
    }
  }

  maze[x][y] = 1;
}

const output = [];

move(maze, 0, 0, "", output);

console.log(output);