Rat in a Maze Problem in DSA C

Mental Model

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

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

Maze grid:
1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1

1 = open path, 0 = wall
Start at top-left (0,0), goal at bottom-right (3,3)

Dry Run Walkthrough

Input: maze: 4x4 grid with 1=open path, 0=wall Start: (0,0), Goal: (3,3)

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

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

Path matrix:
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Why: We begin from the start cell which is open

Step 2: Move right to (0,1) - blocked (0), backtrack

Path matrix unchanged:
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Why: Cannot move right due to wall, so try other directions

Step 3: Move down to (1,0), mark as part of path

Path matrix:
1 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0

Why: Down cell is open, so continue path there

Step 4: Move right to (1,1), mark as part of path

Path matrix:
1 0 0 0
1 1 0 0
0 0 0 0
0 0 0 0

Why: Right cell is open, continue path

Step 5: Move down to (2,1), mark as part of path

Path matrix:
1 0 0 0
1 1 0 0
0 1 0 0
0 0 0 0

Why: Down cell is open, continue path

Step 6: Move down to (3,1), mark as part of path

Path matrix:
1 0 0 0
1 1 0 0
0 1 0 0
0 1 0 0

Why: Down cell is open, continue path

Step 7: Move right to (3,2), mark as part of path

Path matrix:
1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 0

Why: Right cell is open, continue path

Step 8: Move right to (3,3), mark as part of path - goal reached

Path matrix:
1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1

Why: Reached goal cell, path found

Result:

Path matrix:
1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1
Path found from start to goal

Annotated Code

DSA C

#include <stdio.h>
#define N 4

int isSafe(int maze[N][N], int x, int y) {
    return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}

int solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]) {
    if (x == N - 1 && y == N - 1 && maze[x][y] == 1) {
        sol[x][y] = 1; // mark goal cell
        return 1;
    }

    if (isSafe(maze, x, y) == 1) {
        if (sol[x][y] == 1) // already part of path
            return 0;

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

        if (solveMazeUtil(maze, x + 1, y, sol) == 1) // move down
            return 1;

        if (solveMazeUtil(maze, x, y + 1, sol) == 1) // move right
            return 1;

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

    return 0;
}

void printSolution(int sol[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", sol[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int maze[N][N] = {
        {1, 0, 0, 0},
        {1, 1, 0, 0},
        {0, 1, 0, 0},
        {0, 1, 1, 1}
    };

    int sol[N][N] = {0};

    if (solveMazeUtil(maze, 0, 0, sol) == 1) {
        printSolution(sol);
    } else {
        printf("No path found\n");
    }

    return 0;
}

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

Check if current cell is goal and open

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

Mark cell as part of solution path

if (solveMazeUtil(maze, x + 1, y, sol) == 1) // move down

Try moving down recursively

if (solveMazeUtil(maze, x, y + 1, sol) == 1) // move right

Try moving right recursively

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

Remove cell from path if no way forward

Output

1 0 0 0 

1 1 0 0 

0 1 0 0 

0 1 1 1 

Complexity Analysis

Time: O(2^(N*N)) because in worst case each cell can lead to two recursive calls exploring 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 approach explores paths deeply and may be slower but simpler to implement

Edge Cases

Empty maze (all zeros)

No path found, function returns 0

DSA C

if (isSafe(maze, x, y) == 1) {

Start or goal cell blocked

No path found immediately

DSA C

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

Single cell maze open

Path found immediately

DSA C

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

When to Use This Pattern

When you see a grid with blocked and open cells and need to find a path from start to end, use backtracking to explore possible routes step-by-step.

Common Mistakes

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

Mistake: Trying to move outside grid boundaries
Fix: Check boundaries with isSafe before moving

Summary

Finds a path through a maze grid from start to goal by moving only through open cells.

Use when you need to explore all possible paths in a grid to find a valid route.

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?

easy

A. Calculate the shortest distance between two points in a maze

B. Count the number of walls in the maze

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

D. Fill the maze with numbers

Solution

1. Step 1: Understand the problem statement

   The Rat in a Maze problem asks to find a path from the start (usually top-left) to the destination (usually bottom-right) in a maze represented by a grid.

2. Step 2: Identify the goal

   The goal is to find any valid path through open cells (usually marked 1) avoiding blocked cells (usually marked 0).

3. Final Answer:

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

4. Quick Check:

   Goal = Find path [OK]

Hint: Look for pathfinding from start to end in the maze [OK]

Common Mistakes:

• Thinking it's about counting walls
• Confusing with shortest path calculation
• Assuming maze filling is required

2. Which of the following is the correct way to declare the maze matrix in C for a 4x4 maze?

easy

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

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

C. int maze[][] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}};

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

Solution

1. Step 1: Understand C array declaration syntax

   In C, a 2D array must have both dimensions specified except for the first dimension if initialized immediately. Here, both dimensions are specified as 4.

2. Step 2: Check initialization format

   int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}}; correctly declares a 4x4 int array with nested braces for each row.

3. Final Answer:

   int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}}; -> Option A

4. Quick Check:

   Correct 2D array syntax = int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}}; [OK]

Hint: Use nested braces for each row in 2D array initialization [OK]

Common Mistakes:

• Omitting second dimension size
• Using single braces for all elements
• Declaring incomplete array sizes

3. What will be the output of the following code snippet for the Rat in a Maze problem?

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

int solution[4][4] = {0};

int solveMaze(int maze[4][4], int x, int y, int solution[4][4]) {
  if (x == 3 && y == 3 && maze[x][y] == 1) {
    solution[x][y] = 1;
    return 1;
  }
  if (x >= 0 && x < 4 && y >= 0 && y < 4 && maze[x][y] == 1) {
    solution[x][y] = 1;
    if (solveMaze(maze, x + 1, y, solution)) return 1;
    if (solveMaze(maze, x, y + 1, solution)) return 1;
    solution[x][y] = 0;
    return 0;
  }
  return 0;
}

int main() {
  if (solveMaze(maze, 0, 0, solution)) {
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        printf("%d ", solution[i][j]);
      }
      printf("\n");
    }
  } else {
    printf("No path found\n");
  }
  return 0;
}

medium

A. 1 0 0 0
0 1 0 0
0 1 0 0
0 1 1 1

B. 1 0 0 0
1 1 0 1
0 1 0 0
1 1 1 1

C. No path found

D. 1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1

Solution

1. Step 1: Trace the recursive calls

   The function tries to move right (x+1, y) first, then down (x, y+1). It marks path cells in solution matrix if maze cell is 1.

2. Step 2: Follow the path found

   Starting at (0,0), path moves down to (1,0), then right to (1,1), down to (2,1), down to (3,1), right to (3,2), right to (3,3). This path is marked with 1s in solution.

3. Final Answer:

   1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 -> Option D

4. Quick Check:

   Path marked in solution matrix = 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 [OK]

Hint: Trace recursion path marking 1s in solution matrix [OK]

Common Mistakes:

• Confusing row and column indices
• Assuming path includes blocked cells
• Ignoring backtracking step

4. Identify the bug in the following solveMaze function and select the correct fix.

int solveMaze(int maze[4][4], int x, int y, int solution[4][4]) {
  if (x == 3 && y == 3 && maze[x][y] == 1) {
    solution[x][y] = 1;
    return 1;
  }
  if (x >= 0 && x < 4 && y >= 0 && y < 4 && maze[x][y] == 1) {
    solution[x][y] = 1;
    if (solveMaze(maze, x + 1, y, solution)) return 1;
    if (solveMaze(maze, x, y + 1, solution)) return 1;
    return 0;
  }
  return 0;
}

medium

A. Change base case to check (x == 4 && y == 4)

B. Add backtracking step: set solution[x][y] = 0 before returning 0

C. Remove the check maze[x][y] == 1

D. Change recursive calls order to (x, y + 1) then (x + 1, y)

Solution

1. Step 1: Identify missing backtracking

   The function marks solution[x][y] = 1 but does not reset it to 0 if path fails, causing incorrect path marking.

2. Step 2: Fix by adding backtracking

   Before returning 0, set solution[x][y] = 0 to unmark the cell and allow other paths to be explored.

3. Final Answer:

   Add backtracking step: set solution[x][y] = 0 before returning 0 -> Option B

4. Quick Check:

   Backtracking needed to unmark path [OK]

Hint: Always unmark path cell if dead end found [OK]

Common Mistakes:

• Forgetting to unmark solution cell
• Incorrect base case coordinates
• Changing recursion order without reason

5. Given a 5x5 maze where 0 represents blocked cells and 1 represents open cells, how would you modify the Rat in a Maze algorithm to find all possible paths from start (0,0) to end (4,4)?

hard

A. Modify the function to explore all directions and store each valid path in a list

B. Stop recursion after finding the first path and return immediately

C. Use a queue instead of recursion to find one path only

D. Change maze values from 1 to 2 to mark visited cells permanently

Solution

1. Step 1: Understand requirement to find all paths

   Finding all paths means exploring every possible route from start to end without stopping at first success.

2. Step 2: Modify algorithm to explore all directions and store paths

   Change recursion to continue after finding a path, store each valid path in a list or array, and backtrack properly to explore other routes.

3. Final Answer:

   Modify the function to explore all directions and store each valid path in a list -> Option A

4. Quick Check:

   All paths require full exploration [OK]

Hint: Explore all routes and save paths, don't stop at first success [OK]

Common Mistakes:

• Stopping after first path found
• Marking visited cells permanently blocking other paths
• Using BFS without path storage