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)).