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

You're given an n x n maze, where n is odd, filled with movement values. Starting from any of the four corner cells, find every path that leads to the maze's center cell at (n/2, n/2) (integer division). From a cell (i, j), you must move exactly maze[i][j] steps in a single direction — up, down, left, or right — landing on the next cell in that path; a cell already visited on the current path cannot be revisited, and moves that go outside the grid are not allowed.

Edge cases: A given corner may have no valid path to the center at all. When n = 1, the single corner cell is itself the center.

Input Format
Implement findPaths(maze). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter.

Sample Input and Output

Example 1 · Run Sample

Input
maze = [[0]]
Output
[[[0,0]]]

Example 2

Input
maze = [[0,0,0],[0,0,0],[0,0,0]]
Output
[]
Constraints
  • 1 <= n <= 9
  • n is odd
Test Cases (2)
Case 1
Args: [[[0]]] Expected: [[[0,0]]]
Case 2
Args: [[[0,0,0],[0,0,0],[0,0,0]]] Expected: []
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.

javascript
function findPaths(maze) {
  const n = maze.length;
  const mid = Math.floor(n / 2);
  const results = [];
  const corners = n === 1 ? [[0, 0]] : [[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