Rat in a Maze Problem in DSA C# - Build from Scratch

Rat in a Maze Problem

📖 Scenario: Imagine a small rat trying to find its way through a maze to reach the cheese. The maze is a grid where some cells are open paths and others are walls. The rat can only move right or down. We want to help the rat find a path from the top-left corner to the bottom-right corner.

🎯 Goal: You will create a program that represents the maze as a 2D array, set up a variable to track the size of the maze, write a function to find a path for the rat, and finally print the path found.

📋 What You'll Learn

Create a 2D integer array called maze with the exact values given.

Create an integer variable called n to store the size of the maze.

Write a function called FindPath that uses recursion to find a path from the start to the end.

Print the path matrix showing the route the rat takes.

💡 Why This Matters

🌍 Real World

Maze solving algorithms are used in robotics for path planning and navigation in unknown environments.

💼 Career

Understanding recursion and pathfinding is important for software roles involving algorithms, game development, and robotics.

1

Create the maze grid

Create a 2D integer array called maze with these exact values: {{1, 0, 0, 0}, {1, 1, 0, 1}, {0, 1, 0, 0}, {1, 1, 1, 1}}

DSA C#

// Create the maze 2D array
// Your code here

Hint

Use int[,] to create a 2D array and assign the exact values as shown.

2

Set the maze size

Create an integer variable called n and set it to the length of one side of the maze using maze.GetLength(0)

DSA C#

int[,] maze = new int[,] {
    {1, 0, 0, 0},
    {1, 1, 0, 1},
    {0, 1, 0, 0},
    {1, 1, 1, 1}
};
// Create variable n for maze size
// Your code here

Hint

Use maze.GetLength(0) to get the number of rows (or columns) since the maze is square.

3

Write the path finding function

Write a recursive function called FindPath that takes parameters maze, n, row, col, and path. It should return true if a path is found from (row, col) to the bottom-right corner, moving only right or down through cells with value 1. Mark the path in path by setting path[row, col] = 1.

DSA C#

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

int n = maze.GetLength(0);

// Write the FindPath function below
// Your code here

Hint

Use recursion to try moving down and right. Mark the path in the path array. Backtrack if no path found.

4

Find and print the path

Create a 2D integer array called path of size n x n initialized with zeros. Call FindPath(maze, n, 0, 0, path). Then print the path matrix row by row, with values separated by spaces.

DSA C#

Hint

Create a path array filled with zeros. Call FindPath starting at (0,0). If a path is found, print the path matrix row by row.

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