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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rat in a Maze Path

What is the output path printed by this Rat in a Maze code when the maze is solved?

DSA C#

using System;

class MazeSolver {
    static int N = 4;

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

    static bool SolveMazeUtil(int[,] maze, int x, int y, int[,] sol) {
        if (x == N - 1 && y == N - 1 && maze[x, y] == 1) {
            sol[x, y] = 1;
            return true;
        }

        if (IsSafe(maze, x, y)) {
            if (sol[x, y] == 1) return false;

            sol[x, y] = 1;

            if (SolveMazeUtil(maze, x + 1, y, sol)) return true;

            if (SolveMazeUtil(maze, x, y + 1, sol)) return true;

            sol[x, y] = 0;
            return false;
        }

        return false;
    }

    public static void SolveMaze(int[,] maze) {
        int[,] sol = new int[N, N];

        if (!SolveMazeUtil(maze, 0, 0, sol)) {
            Console.WriteLine("No solution");
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                Console.Write(sol[i, j] + " ");
            }
            Console.WriteLine();
        }
    }

    static void Main() {
        int[,] maze = {
            {1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {1, 1, 1, 1}
        };

        SolveMaze(maze);
    }
}

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

B [[1,0,0,0],[1,1,0,1],[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],[1,1,0,0],[0,0,0,0],[1,1,1,1]]

💡 Hint

Trace the path from top-left to bottom-right marking 1s where the rat can move down or right safely.

The rat moves down first, then right, avoiding blocked cells (0). The solution matrix marks the path with 1s showing the route taken.

❓ Predict Output

intermediate

Number of Steps in Rat in a Maze Path

How many steps does the rat take in the solution path printed by the code below?

DSA C#

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

// The solution path is marked by 1s in the output matrix from previous code.

A 7

B 6

C 8

D 5

💡 Hint

Count the number of 1s in the solution matrix representing the path.

The path includes 7 cells marked 1 in the solution matrix, representing 7 steps from start to finish.

🔧 Debug

advanced

Identify the Error in Maze Solver Code

What error will this code produce when run?

DSA C#

static bool SolveMazeUtil(int[,] maze, int x, int y, int[,] sol) {
    if (x == N - 1 && y == N - 1 && maze[x, y] == 1) {
        sol[x, y] = 1;
        return true;
    }

    if (IsSafe(maze, x, y)) {
        if (sol[x, y] == 1) return false;

        sol[x, y] = 1;

        if (SolveMazeUtil(maze, x + 1, y, sol)) return true;

        if (SolveMazeUtil(maze, x, y + 1, sol)) return true;

        sol[x, y] = 0;
        return false;
    }

    return false;
}

// Note: N is not defined anywhere in this snippet.

A Compile-time error: 'N' does not exist in the current context

B No error, code runs and finds a path

C Logical error: The path includes blocked cells

D Runtime error: StackOverflowException due to infinite recursion

💡 Hint

Check if all variables used are declared and accessible.

The variable N is used but not declared or passed, causing a compile-time error.

🧠 Conceptual

advanced

Why Backtracking is Used in Rat in a Maze Problem?

Why is backtracking the preferred technique to solve the Rat in a Maze problem?

A Because it uses greedy approach to pick the next best step

B Because it uses dynamic programming to store intermediate results

C Because it sorts the maze cells to find the shortest path

D Because it tries all possible paths and abandons paths that lead to dead ends

💡 Hint

Think about how the algorithm explores paths and handles failures.

Backtracking explores all paths and backtracks when a path is invalid, ensuring all possibilities are checked.

🚀 Application

expert

Modify Maze to Block Shortest Path

Given the original maze below, which modification blocks the shortest path forcing the rat to take a longer route?

DSA C#

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

A Change maze[1,1] from 1 to 0

B Change maze[2,1] from 1 to 0

C Change maze[0,0] from 1 to 0

D Change maze[3,0] from 1 to 0

💡 Hint

Identify the shortest path and block a critical cell on it.

Blocking maze[2,1] cuts the direct path forcing the rat to find a longer alternative route.

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