Find paths from corner cell to middle cell in maze Hard 0 attempts
GeeksforGeeks ↗

Find paths from corner cell to middle cell in maze

Hard BacktrackingRecursion GeeksforGeeks

Given an n x n maze (where n is odd), find all paths from any corner cell to the center cell (n/2, n/2). From cell (i, j), you must move exactly maze[i][j] steps in one of the four cardinal directions (up, down, left, right). You cannot revisit a cell in the same path.

Example 1:

Input: maze = [
  [3, 5, 4, 4, 7],
  [3, 1, 3, 3, 1],
  [3, 2, 3, 1, 2],
  [6, 3, 1, 5, 3],
  [1, 2, 3, 4, 1]
]
Output: One valid path from (0,0): (0,0) → (0,3) → (0,7 invalid)... 
The paths vary; the goal is to reach (2,2) from corners.

Example 2:

Input: maze = [
  [2, 1, 3],
  [1, 1, 1],
  [3, 1, 2]
]
Output: Paths from (0,0) to (1,1): (0,0)→(0,2)→(0,2 can't, bounds)

Edge cases: No valid path exists from a given corner. Maze with size 1 — the corner is the center.

Sample Input
maze = [[3, 5, 4, 4, 7, 3, 4, 6, 3], [6, 7, 5, 6, 6, 2, 0, 3, 1], [3, 3, 4, 6, 1, 2, 4, 6, 5], [2, 4, 5, 6, 8, 5, 6, 5, 1], [2, 3, 2, 4, 0, 4, 2, 6, 2], [6, 5, 3, 2, 4, 3, 2, 6, 1], [1, 3, 5, 7, 8, 3, 2, 4, 3], [6, 1, 1, 0, 1, 2, 1, 0, 7], [1, 3, 2, 2, 1, 0, 8, 5, 1]]
Sample Output
[(0,0) -> (0,3) -> (0,7) -> (6,7) -> (6,3) -> (3,3) -> (3,5) -> (6,5) -> (6,2) -> (2,2) -> (2,6) -> (4,6) -> (4,4)]
Constraints
  • 1 <= n <= 9
  • n is odd
Topics
BacktrackingRecursion

Approach: DFS Backtracking

Start DFS from each corner cell. At each cell, try jumping exactly maze[i][j] steps in all four directions. Mark cells as visited to avoid cycles, and backtrack when a direction leads nowhere. Collect the path when you reach the center.

function findPaths(maze) {
  const n = maze.length;
  const mid = Math.floor(n / 2);
  const results = [];
  const corners = [[0, 0], [0, n - 1], [n - 1, 0], [n - 1, n - 1]];
  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  function dfs(r, c, path, visited) {
    if (r === mid && c === mid) {
      results.push([...path]);
      return;
    }

    const steps = maze[r][c];
    for (const [dr, dc] of dirs) {
      const nr = r + dr * steps;
      const nc = c + dc * steps;
      if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
      const key = nr * n + nc;
      if (visited.has(key)) continue;

      visited.add(key);
      path.push([nr, nc]);
      dfs(nr, nc, path, visited);
      path.pop();
      visited.delete(key);
    }
  }

  for (const [sr, sc] of corners) {
    const key = sr * n + sc;
    dfs(sr, sc, [[sr, sc]], new Set([key]));
  }
  return results;
}

Time Complexity: O(4^(n²)) worst case — each cell has up to 4 choices, but visited pruning keeps it manageable

Space Complexity: O(n²) for the visited set and recursion stack

Saved in this browser only. Private to you.

JavaScript