Rat in a Maze Problem in DSA C++

Mental Model

Find a path from start to finish in a grid by moving step-by-step through allowed cells.

Analogy: Imagine a rat trying to find cheese in a maze by moving only through open paths and avoiding walls.

S -> 0 1 0
0 -> 0 0 0
0 0 0 -> E

S = start, E = end, 0 = open path, 1 = wall

Dry Run Walkthrough

Input: maze: 3x3 grid with 0 as open path and 1 as wall Start at top-left (0,0), end at bottom-right (2,2) Maze: 0 0 1 0 0 0 1 0 0

Goal: Find one path from start to end moving only right or down through open cells

Step 1: Start at (0,0), mark as path

[S] 0 1
0 0 0
1 0 0

Why: We begin from the start cell

Step 2: Move right to (0,1), mark as path

S [0] 1
0 0 0
1 0 0

Why: Right cell is open, so move forward

Step 3: Try moving right to (0,2), blocked by wall

S [0] 1
0 0 0
1 0 0

Why: Cannot move into wall, so try down from (0,1)

Step 4: Move down to (1,1), mark as path

S [0] 1
0 [0] 0
1 0 0

Why: Down cell is open, continue path

Step 5: Move right to (1,2), mark as path

S 0 1
0 0 [0]
1 0 0

Why: Right cell is open, move forward

Step 6: Move down to (2,2), mark as path and reach end

S 0 1
0 0 0
1 0 [E]

Why: Reached the destination

Result:

Path found: (0,0) -> (0,1) -> (1,1) -> (1,2) -> (2,2)

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

bool isSafe(int x, int y, int n, vector<vector<int>>& maze, vector<vector<int>>& sol) {
    return (x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == 0 && sol[x][y] == 0);
}

bool solveMazeUtil(int x, int y, int n, vector<vector<int>>& maze, vector<vector<int>>& sol) {
    if (x == n - 1 && y == n - 1 && maze[x][y] == 0) {
        sol[x][y] = 1; // mark end as part of path
        return true;
    }
    if (isSafe(x, y, n, maze, sol)) {
        sol[x][y] = 1; // mark current cell as part of path
        if (solveMazeUtil(x, y + 1, n, maze, sol)) // move right
            return true;
        if (solveMazeUtil(x + 1, y, n, maze, sol)) // move down
            return true;
        sol[x][y] = 0; // backtrack
        return false;
    }
    return false;
}

void printSolution(vector<vector<int>>& sol) {
    int n = sol.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << sol[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    vector<vector<int>> maze = {
        {0, 0, 1},
        {0, 0, 0},
        {1, 0, 0}
    };
    int n = maze.size();
    vector<vector<int>> sol(n, vector<int>(n, 0));
    if (solveMazeUtil(0, 0, n, maze, sol)) {
        printSolution(sol);
    } else {
        cout << "No path found" << endl;
    }
    return 0;
}

if (x == n - 1 && y == n - 1 && maze[x][y] == 0) {

Check if current cell is destination

if (isSafe(x, y, n, maze, sol)) {

Check if current cell is safe to move

sol[x][y] = 1; // mark current cell as part of path

Mark current cell as part of solution path

if (solveMazeUtil(x, y + 1, n, maze, sol))

Try moving right recursively

if (solveMazeUtil(x + 1, y, n, maze, sol))

Try moving down recursively

sol[x][y] = 0; // backtrack

Backtrack if no path found from current cell

Output

1 1 0 

0 1 1 

0 0 1 

Complexity Analysis

Time: O(2^(n*n)) because in worst case, each cell can lead to two moves and we explore all paths

Space: O(n*n) for the solution matrix and recursion stack in worst case

vs Alternative: Compared to BFS which uses a queue and can find shortest path, this DFS backtracking explores all paths and may be slower

Edge Cases

Empty maze (0x0)

No path to find, function returns false

DSA C++

if (x == n - 1 && y == n - 1) {

Start or end cell blocked

No path found because start or end is not safe

DSA C++

if (isSafe(x, y, n, maze, sol)) {

Maze with no possible path

Backtracking explores all options and returns no path

DSA C++

sol[x][y] = 0; // backtrack

When to Use This Pattern

When you see a grid and need to find a path from one point to another with constraints, use backtracking to explore all possible paths step-by-step.

Common Mistakes

Mistake: Not marking cells as visited leading to infinite loops
Fix: Mark cells as part of path before recursive calls and unmark on backtrack

Mistake: Trying to move outside maze boundaries
Fix: Check boundaries in isSafe function before moving

Summary

Finds a path through a maze from start to end using backtracking.

Use when you need to explore all possible paths in a grid with obstacles.

The key is to try moves step-by-step, mark path, and backtrack if stuck.

Practice

1. What is the main goal of the Rat in a Maze Problem in Data Structures & Algorithms?

easy

A. Find a path from the start to the destination in a maze

B. Count the number of walls in the maze

C. Calculate the shortest distance between two points in a graph

D. Sort the maze cells in ascending order

Solution

1. Step 1: Understand the problem context

   The Rat in a Maze problem involves navigating a maze represented by a grid to find a path from the start cell to the destination cell.

2. Step 2: Identify the main objective

   The main objective is to find a valid path through open cells (usually marked as 1) from the start to the end point.

3. Final Answer:

   Find a path from the start to the destination in a maze -> Option A

4. Quick Check:

   Goal = Find path [OK]

Hint: Focus on pathfinding, not counting or sorting [OK]

Common Mistakes:

• Confusing pathfinding with counting walls
• Thinking it's about sorting cells
• Assuming it's about shortest distance always

2. Which of the following is the correct way to declare a 2D maze array of size 4x4 in C++?

easy

A. int maze[4][4];

B. int maze(4,4);

C. int maze[4,4];

D. int maze{4,4};

Solution

1. Step 1: Recall C++ array declaration syntax

   In C++, a 2D array is declared using square brackets for each dimension, like int maze[4][4];.

2. Step 2: Analyze each option

   int maze[4][4]; uses correct syntax. int maze(4,4); uses parentheses which is invalid for arrays. int maze[4,4]; uses comma inside brackets which is incorrect. int maze{4,4}; uses braces which is invalid for declaration.

3. Final Answer:

   int maze[4][4]; -> Option A

4. Quick Check:

   2D array = int maze[4][4]; [OK]

Hint: Use square brackets for array dimensions [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Using commas inside brackets
• Using braces for declaration

3. Consider the following C++ code snippet for a 2x2 maze where 1 means open path and 0 means blocked:

int maze[2][2] = {{1, 0}, {1, 1}};
bool solveMaze(int maze[2][2], int x, int y) {
  if (x == 1 && y == 1) return true;
  if (x < 0 || y < 0 || x >= 2 || y >= 2 || maze[x][y] == 0) return false;
  if (solveMaze(maze, x + 1, y)) return true;
  if (solveMaze(maze, x, y + 1)) return true;
  return false;
}
int main() {
  bool result = solveMaze(maze, 0, 0);
  std::cout << (result ? "Path Found" : "No Path") << std::endl;
  return 0;
}

What will be the output when this program runs?

medium

A. Runtime Error

B. No Path

C. Compilation Error

D. Path Found

Solution

1. Step 1: Trace the recursive calls starting at (0,0)

   At (0,0), maze[0][0] = 1 (open). Try moving down to (1,0): maze[1][0] = 1 (open). From (1,0), try moving down to (2,0) invalid, then right to (1,1): maze[1][1] = 1 (open) and is destination.

2. Step 2: Confirm path existence

   Since (1,1) is reached, function returns true and prints "Path Found".

3. Final Answer:

   Path Found -> Option D

4. Quick Check:

   Valid path exists = Path Found [OK]

Hint: Follow recursion down and right moves [OK]

Common Mistakes:

• Ignoring boundary checks
• Assuming no path due to blocked cell
• Confusing indices order

4. The following code snippet is intended to solve the Rat in a Maze problem but has a bug:

bool solveMaze(int maze[3][3], int x, int y) {
  if (x == 2 && y == 2) return true;
  if (x > 2 || y > 2 || maze[x][y] == 0) return false;
  if (solveMaze(maze, x + 1, y)) return true;
  if (solveMaze(maze, x, y + 1)) return true;
  return false;
}

What is the bug in this code?

medium

A. Missing check for negative indices

B. No check for maze boundaries less than zero

C. No check for visited cells causing infinite recursion

D. Incorrect base case coordinates

Solution

1. Step 1: Analyze boundary and base case checks

   The code checks if x or y are greater than 2 and if the cell is blocked. It returns true if destination (2,2) is reached.

2. Step 2: Identify missing visited check

   There is no mechanism to mark visited cells, so the recursion can revisit the same cells repeatedly, causing infinite recursion or stack overflow.

3. Final Answer:

   No check for visited cells causing infinite recursion -> Option C

4. Quick Check:

   Visited check missing = Infinite recursion [OK]

Hint: Always mark visited cells to avoid loops [OK]

Common Mistakes:

• Ignoring visited cells check
• Assuming boundary checks cover all cases
• Confusing base case with boundary

5. Given a 4x4 maze represented as:

int maze[4][4] = {
  {1, 0, 0, 0},
  {1, 1, 0, 1},
  {0, 1, 0, 0},
  {1, 1, 1, 1}
};

Write a function to find one path from (0,0) to (3,3) moving only right or down. Which of the following describes the correct approach?

hard

A. Use depth-first search but only move left and up

B. Use backtracking to explore right and down moves, marking visited cells to avoid cycles

C. Use breadth-first search without marking visited cells

D. Use a greedy approach always moving right first without backtracking

Solution

1. Step 1: Understand movement constraints and maze structure

   The rat can move only right or down. The maze has blocked cells (0) and open cells (1). We need to find a path from top-left to bottom-right.

2. Step 2: Choose correct algorithm approach

   Backtracking explores all possible paths by moving right or down, marking visited cells to avoid revisiting and infinite loops. Greedy or BFS without visited checks can fail or loop.

3. Final Answer:

   Use backtracking to explore right and down moves, marking visited cells to avoid cycles -> Option B

4. Quick Check:

   Backtracking + visited = Correct approach [OK]

Hint: Backtrack with visited marks for safe pathfinding [OK]

Common Mistakes:

• Using greedy without backtracking
• Ignoring visited cells causing loops
• Moving in wrong directions