Rat in a Maze Problem in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rat Path in a 4x4 Maze

What is the output path of the rat in the maze after running the given code? The rat starts at (0,0) and can move only right or down through cells with value 1.

DSA C

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 && y >= 0 && x < 4 && 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;
}

A [[1,0,0,0],[1,1,0,1],[0,1,0,0],[1,1,1,1]]

B [[1,0,0,0],[1,0,0,0],[0,1,0,0],[1,1,1,1]]

C [[1,0,0,0],[1,1,0,0],[0,1,0,0],[0,1,1,1]]

D [[1,0,0,0],[0,1,0,0],[0,1,0,0],[1,1,1,1]]

💡 Hint

Trace the path by moving only right or down through cells with value 1.

The rat moves down from (0,0) to (1,0), then right to (1,1), down to (2,1), and finally down and right to reach (3,3). The solution matrix marks these cells with 1.

🧠 Conceptual

intermediate

Understanding Rat Movement Constraints

In the Rat in a Maze problem, if the rat can move only right and down, which of the following statements is true about the possible paths?

A The rat can only reach cells that are connected through a path of 1s moving right or down.

B The rat can move diagonally to reach the destination faster.

C The rat can reach any cell in the maze regardless of obstacles.

D The rat can move left and up to backtrack and find alternative paths.

💡 Hint

Consider the allowed moves and the maze layout.

The rat can only move right or down through cells with value 1, so it can only reach cells connected by such paths.

🔧 Debug

advanced

Identify the Bug in Maze Solver Code

What error will occur when running this code snippet for the Rat in a Maze problem?

DSA C

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 && y >= 0 && x < 4 && 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;
}

A Stack overflow due to infinite recursion

B No error, code runs correctly

C Compilation error due to missing return statement

D Runtime error due to accessing invalid array index

💡 Hint

Check if the code backtracks properly when a path is invalid.

The code does not reset solution[x][y] to 0 when backtracking, causing infinite recursion and stack overflow.

🚀 Application

advanced

Number of Paths in a Maze with Obstacles

Given a 3x3 maze where 1 represents open path and 0 represents obstacle: int maze[3][3] = { {1, 1, 0}, {1, 1, 1}, {0, 1, 1} }; How many unique paths exist from top-left (0,0) to bottom-right (2,2) moving only right or down?

A 5

B 2

C 4

D 3

💡 Hint

Count all paths moving right/down avoiding zeros.

There are three unique paths avoiding obstacles: (0,0)->(0,1)->(1,1)->(1,2)->(2,2), (0,0)->(1,0)->(1,1)->(1,2)->(2,2), and (0,0)->(1,0)->(1,1)->(2,1)->(2,2).

🧠 Conceptual

expert

Time Complexity of Rat in a Maze Backtracking Algorithm

What is the worst-case time complexity of the backtracking solution for the Rat in a Maze problem on an N x N maze?

A O(2N)

B O(2^(N^2))

C O(N!)

D O(N^2)

💡 Hint

Consider that each cell can be either part of the path or not, and the rat can move in two directions.

In the worst case, the rat explores all possible paths through the maze, which can be exponential in the number of cells, i.e., O(2^(N^2)).

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