DEV Community

Dev Cookies
Dev Cookies

Posted on

Blog 7: Path Search & Maze Pattern Problems 🏞️

Maze and path search problems are graph traversal + backtracking at their core. You explore possible paths in a grid/graph, mark visited nodes, backtrack when stuck, and record valid paths.

These problems are excellent for learning how DFS + backtracking works in practice.

🔹 Problem 1: Rat in a Maze

Classic problem: given a square maze with open cells (1) and blocked cells (0), find all possible paths from the top-left (0,0) to the bottom-right (n-1,n-1).

Example Maze 

1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1
Enter fullscreen mode Exit fullscreen mode

Output paths (as directions):

DDRDRR
DRDDRR
Enter fullscreen mode Exit fullscreen mode

Java Implementation 

import java.util.*;

public class RatInMaze {
    private static final int[] rowDir = {1, 0, 0, -1}; // D, L, R, U
    private static final int[] colDir = {0, -1, 1, 0};
    private static final char[] move = {'D', 'L', 'R', 'U'};

    public static List<String> findPaths(int[][] maze, int n) {
        List<String> result = new ArrayList<>();
        if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return result;

        boolean[][] visited = new boolean[n][n];
        backtrack(0, 0, maze, n, visited, new StringBuilder(), result);
        return result;
    }

    private static void backtrack(int r, int c, int[][] maze, int n,
                                  boolean[][] visited, StringBuilder path, List<String> result) {
        if (r == n - 1 && c == n - 1) {
            result.add(path.toString());
            return;
        }

        visited[r][c] = true;

        for (int i = 0; i < 4; i++) {
            int nr = r + rowDir[i];
            int nc = c + colDir[i];
            if (isSafe(nr, nc, maze, n, visited)) {
                path.append(move[i]);
                backtrack(nr, nc, maze, n, visited, path, result);
                path.deleteCharAt(path.length() - 1); // backtrack
            }
        }

        visited[r][c] = false;
    }

    private static boolean isSafe(int r, int c, int[][] maze, int n, boolean[][] visited) {
        return r >= 0 && c >= 0 && r < n && c < n && maze[r][c] == 1 && !visited[r][c];
    }

    public static void main(String[] args) {
        int[][] maze = {
            {1, 0, 0, 0},
            {1, 1, 0, 1},
            {1, 1, 0, 0},
            {0, 1, 1, 1}
        };
        System.out.println(findPaths(maze, maze.length));
    }
}
Enter fullscreen mode Exit fullscreen mode

🔹 Problem 2: Unique Paths with Obstacles (LeetCode 63)

Count paths from (0,0) to (m-1,n-1) in a grid with obstacles.

  • Unlike “Rat in a Maze”, here we just need number of paths, not path strings.
  • Can be solved with DFS + memoization or DP.

🔹 Problem 3: Shortest Path in Maze (BFS)

Backtracking can find all paths, but for shortest path, BFS is better.

  • Example: LeetCode 1091 (Shortest Path in Binary Matrix).
  • Use BFS instead of DFS for minimum distance.

🔹 Problem 4: All Paths in a DAG (LeetCode 797)

Given a directed acyclic graph (DAG), return all paths from 0 to n-1.

This is essentially the “maze” problem but in graph form.

class AllPaths {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(0);
        dfs(0, graph, path, result);
        return result;
    }

    private void dfs(int node, int[][] graph, List<Integer> path, List<List<Integer>> result) {
        if (node == graph.length - 1) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int next : graph[node]) {
            path.add(next);
            dfs(next, graph, path, result);
            path.remove(path.size() - 1);
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

🔹 Variations of Maze & Path Search Problems

  1. Rat in a Maze with Multiple Jumps – Instead of moving 1 step, move 1..k steps.
  2. Shortest Safe Path – Avoid landmines/traps in grid.
  3. Flood Fill (LeetCode 733) – Classic recursion (paint fill algorithm).
  4. Word Maze – Similar to Word Search, but track path positions.
  5. Hamiltonian Path / Cycle in Grid – Visit all cells exactly once (hard, exponential).

🔹 Key Takeaways

✅ Maze/Path problems are DFS + backtracking at their core.
✅ Record path when you reach destination, backtrack when blocked.
✅ Use BFS when the goal is shortest path.
✅ Path search ideas extend naturally to graphs, grids, and DAGs.

Top comments (0)