Rat in a Maze Problem in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the rat can move to the cell (x, y) inside the maze boundaries.

DSA C#

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

Drag options to blanks, or click blank then click option'

Amaze.GetLength(0)

Bmaze.Length

Cn

Dmaze.GetLength(1)

Attempts:

3 left

💡 Hint

Common Mistakes

Using maze.Length returns total elements, not dimension.

Using n directly without confirming maze size.

The maze is a square matrix of size n x n. To check if x is within bounds, we use maze.GetLength(0) which returns the number of rows.

2fill in blank

medium

Complete the code to move the rat downwards in the maze recursion.

DSA C#

if (SolveMazeUtil(maze, x + [1], y, solution, n)) {
    return true;
}

Drag options to blanks, or click blank then click option'

A0

B-1

C1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 means no movement.

Using -1 moves up, not down.

To move down, we increase the row index by 1, so x + 1.

3fill in blank

hard

Fix the error in marking the current cell as part of the solution path.

DSA C#

solution[x, y] = [1];

Drag options to blanks, or click blank then click option'

A1

B0

C-1

Dx + y

Attempts:

3 left

💡 Hint

Common Mistakes

Marking with 0 removes the path mark.

Using negative values is incorrect.

Marking the cell as 1 means it is part of the path.

4fill in blank

hard

Fill both blanks to backtrack correctly by unmarking the cell and returning false.

DSA C#

solution[x, y] = [1];
return [2];

Drag options to blanks, or click blank then click option'

A0

Btrue

Cfalse

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Returning true after backtracking causes wrong path.

Not unmarking the cell leads to incorrect paths.

Backtracking means unmarking the cell by setting it to 0 and returning false to try other paths.

5fill in blank

hard

Fill all three blanks to complete the recursive calls for moving right and backtracking.

DSA C#

if (SolveMazeUtil(maze, x, y + [1], solution, n)) {
    return [2];
}
solution[x, y] = [3];

Drag options to blanks, or click blank then click option'

A0

Btrue

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 to move right causes no movement.

Returning false prematurely stops search.

Moving right means y + 1, returning true if path found, else unmark cell by setting to 0.

Practice

1. What is the main goal of the Rat in a Maze problem?

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 maze

D. Fill the maze with obstacles

Solution

1. Step 1: Understand the problem statement

   The Rat in a Maze problem requires finding a path from the start point (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 as 1) avoiding blocked cells (marked as 0).

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 from start to end in the maze [OK]

Common Mistakes:

• Thinking it's about counting walls
• Confusing with shortest path calculation
• Assuming the maze needs to be filled

2. Which of the following C# method signatures is correct for a recursive function solving the Rat in a Maze problem?

easy

A. bool SolveMaze(int[,] maze, int x, int y, int[,] solution)

B. void SolveMaze(int maze[][], int x, int y, int solution[][])

C. int SolveMaze(List<int> maze, int x, int y, List<int> solution)

D. bool SolveMaze(int maze[], int x, int y, int solution[])

Solution

1. Step 1: Check parameter types for maze and solution

   In C#, 2D arrays are declared as int[,]. Options A, B, and D use incorrect types like jagged arrays or lists without proper syntax.

2. Step 2: Check return type and parameters

   The recursive function should return bool to indicate success or failure, matching bool SolveMaze(int[,] maze, int x, int y, int[,] solution).

3. Final Answer:

   bool SolveMaze(int[,] maze, int x, int y, int[,] solution) -> Option A

4. Quick Check:

   Correct signature uses int[,] and bool return [OK]

Hint: Use int[,] for 2D arrays and bool return for success [OK]

Common Mistakes:

• Using jagged arrays without proper syntax
• Using List<int> instead of arrays
• Wrong return type for recursion

3. What will be the output of the following code snippet for a 2x2 maze where all cells are open (1)?

int[,] maze = { {1, 1}, {1, 1} };
int[,] solution = new int[2,2];
bool result = SolveMaze(maze, 0, 0, solution);
if (result) {
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      Console.Write(solution[i,j] + " ");
    }
    Console.WriteLine();
  }
} else {
  Console.WriteLine("No path found");
}

medium

A. 1 0
1 1

B. 1 1
0 1

C. No path found

D. 1 1
1 1

Solution

1. Step 1: Understand the maze and solution initialization

   The maze is 2x2 with all cells open (1). The solution array is initially all zeros.

2. Step 2: Trace the SolveMaze function

   The rat starts at (0,0), marks it as 1 in solution, moves right to (0,1), marks it as 1, then moves down to (1,1) which is the destination. The path is (0,0) -> (0,1) -> (1,1). The cell (1,0) remains 0.

3. Final Answer:

   1 1 0 1 -> Option B

4. Quick Check:

   Path marks correct cells as 1 [OK]

Hint: Trace path step-by-step marking solution cells [OK]

Common Mistakes:

• Assuming all cells in solution become 1
• Confusing row and column indices
• Printing 'No path found' incorrectly

4. Identify the error in this snippet of the Rat in a Maze recursive function:

bool SolveMaze(int[,] maze, int x, int y, int[,] solution) {
  if (x == maze.GetLength(0) || y == maze.GetLength(1)) return false;
  if (maze[x, y] == 0) return false;
  solution[x, y] = 1;
  if (x == maze.GetLength(0) - 1 && y == maze.GetLength(1) - 1) return true;
  if (SolveMaze(maze, x + 1, y, solution)) return true;
  if (SolveMaze(maze, x, y + 1, solution)) return true;
  solution[x, y] = 0;
  return false;
}

medium

A. Base case for destination is missing

B. Solution array is not updated correctly

C. Boundary check uses '==' instead of '>=' causing out-of-bounds error

D. Recursive calls do not explore all directions

Solution

1. Step 1: Analyze boundary condition

   The condition if (x == maze.GetLength(0) || y == maze.GetLength(1)) only checks equality, but if x or y exceed bounds, it causes out-of-range errors. It should use '>=' to prevent this.

2. Step 2: Check other parts

   Solution array updates and base case are correct. Recursive calls explore right and down directions properly.

3. Final Answer:

   Boundary check uses '==' instead of '>=' causing out-of-bounds error -> Option C

4. Quick Check:

   Boundary check must prevent index overflow [OK]

Hint: Use '>=' for boundary checks to avoid index errors [OK]

Common Mistakes:

• Using '==' instead of '>=' in boundary checks
• Forgetting to reset solution cell on backtrack
• Missing base case for destination

5. Given a 4x4 maze represented as below, which path will the rat take if it always tries to move right first, then down?

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

Choose the correct solution matrix after the rat finds a path.

hard

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

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

C. 1 0 0 0
1 1 0 0
0 0 0 0
1 1 1 1

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

Solution

1. Step 1: Trace the rat's moves trying right first, then down

   Start at (0,0), mark 1, right (0,1)=0 blocked, down (1,0)=1 mark 1. From (1,0), right (1,1)=1 mark 1. From (1,1), right (1,2)=0 blocked, down (2,1)=1 mark 1. From (2,1), right (2,2)=0 blocked, down (3,1)=1 mark 1. From (3,1), right (3,2)=1 mark 1. From (3,2), right (3,3)=1 mark 1, destination.

2. Step 2: Mark the path in solution matrix

   Cells marked 1 are (0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3). Others remain 0.

3. Final Answer:

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

4. Quick Check:

   Right-first path marks correct cells [OK]

Hint: Simulate moves right then down marking path [OK]

Common Mistakes:

• Marking blocked cells as path
• Incorrect backtracking
• Confusing row and column indices