Rat in a Maze Problem in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the rat can move to the next cell inside the maze boundaries.

DSA Java

boolean isSafe(int x, int y, int N) {
    return (x >= 0 && y >= 0 && x < [1] && y < N);
}

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

A0

BN-1

CN+1

DN

Attempts:

3 left

💡 Hint

Common Mistakes

Using N-1 instead of N causes off-by-one errors.

Not checking for negative indices.

The maze size is N x N, so the valid indices are from 0 to N-1. We check if x and y are less than N to stay inside the maze.

2fill in blank

medium

Complete the code to mark the current cell as part of the solution path.

DSA Java

void solveMazeUtil(int maze[][], int x, int y, int sol[][], int N) {
    if (x == N - 1 && y == N - 1) {
        sol[x][y] = [1];
        return;
    }
}

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

A1

B0

C-1

DN

Attempts:

3 left

💡 Hint

Common Mistakes

Marking with 0 which means no path.

Using negative numbers which are invalid here.

We mark the cell as 1 to indicate it is part of the solution path.

3fill in blank

hard

Fix the error in the recursive call to move right in the maze.

DSA Java

if (isSafe(x, y + 1, N) && maze[x][y + 1] == 1) {
    solveMazeUtil(maze, x, [1], sol, N);
}

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

Ay + 1

By

Cx + 1

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Using x + 1 instead of y + 1.

Not updating the coordinate correctly.

To move right, we increase the y coordinate by 1, so the recursive call should use y + 1.

4fill in blank

hard

Fill both blanks to move down and backtrack correctly in the maze.

DSA Java

if (isSafe(x + 1, y, N) && maze[x + 1][y] == 1) {
    solveMazeUtil(maze, [1], [2], sol, N);
}
sol[x][y] = 0; // backtrack

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

Ax + 1

By + 1

Cy

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping x and y coordinates.

Not backtracking properly.

To move down, increase x by 1 and keep y the same. Backtracking resets the current cell to 0.

5fill in blank

hard

Fill all three blanks to complete the base case and recursive calls for the rat in a maze.

DSA Java

if (x == N - 1 && y == N - 1) {
    sol[x][y] = [1];
    return true;
}

if (isSafe(x, y, N) && maze[x][y] == 1) {
    sol[x][y] = [2];
    if (solveMazeUtil(maze, x + 1, y, sol, N))
        return true;
    if (solveMazeUtil(maze, x, y + 1, sol, N))
        return true;
    sol[x][y] = [3]; // backtrack
}
return false;

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

A1

B0

C-1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using -1 or 2 which are invalid markers.

Not backtracking correctly.

Mark the path with 1, and backtrack by resetting the cell to 0.

Practice

1. What is the main goal of the Rat in a Maze Problem in data structures?

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 graph

D. Sort the maze cells in ascending order

Solution

1. Step 1: Understand the problem goal

   The Rat in a Maze problem asks to find a path from the start cell (usually top-left) to the destination cell (usually bottom-right) in a maze represented by a grid.

2. Step 2: Identify the correct goal

   Among the options, only finding a path from start to destination matches the problem's main goal.

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: Remember: Rat must find a path through the maze [OK]

Common Mistakes:

• Confusing path finding with counting walls
• Thinking it's about sorting or distances
• Ignoring the start and destination points

2. Which of the following is the correct way to check if a cell (x, y) is safe to move in a maze represented by a 2D array maze in Java?

easy

A. if (x > 0 && y > 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0)

B. if (x > 0 && y > 0 && x <= maze.length && y <= maze[0].length && maze[x][y] == 0)

C. if (x >= 0 && y >= 0 && x <= maze.length && y <= maze[0].length && maze[x][y] == 1)

D. if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 1)

Solution

1. Step 1: Check valid indices in 2D array

   Indices must be >= 0 and less than maze.length and maze[0].length to avoid ArrayIndexOutOfBoundsException.

2. Step 2: Check if cell is open (usually 1 means open)

   We check if maze[x][y] == 1 to confirm the cell is safe to move.

3. Final Answer:

   if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 1) -> Option D

4. Quick Check:

   Bounds + open cell = if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 1) [OK]

Hint: Check indices >=0 and < length, and cell == 1 [OK]

Common Mistakes:

• Using > 0 instead of >= 0 causes skipping first row/column
• Using <= length causes index out of bounds
• Checking for 0 instead of 1 for open path

3. What will be the output path for the following maze if the rat starts at (0,0) and destination is (1,2)?

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

Assuming the rat moves only right or down and marks path cells with 2, what is the maze after the path is found?

medium

A. [[1, 0, 0], [2, 2, 2]]

B. [[2, 0, 0], [2, 2, 2]]

C. [[2, 0, 0], [1, 1, 2]]

D. [[2, 0, 0], [2, 1, 2]]

Solution

1. Step 1: Trace the path from (0,0) to (1,2)

   Start at (0,0) which is 1, move down to (1,0) = 1, then right to (1,1) = 1, then right to (1,2) = 1.

2. Step 2: Mark the path cells with 2

   Mark (0,0), (1,0), (1,1), (1,2) as 2. Other cells remain unchanged.

3. Final Answer:

   [[2, 0, 0], [2, 2, 2]] -> Option B

4. Quick Check:

   Path marked with 2 = [[2, 0, 0], [2, 2, 2]] [OK]

Hint: Follow path down then right, mark visited cells [OK]

Common Mistakes:

• Marking cells not in path
• Confusing 0 and 1 cells
• Not marking start cell

4. Given the following code snippet for the Rat in a Maze problem, what is the error?

boolean solveMaze(int[][] maze, int x, int y, int[][] solution) {
  if (x == maze.length - 1 && y == maze[0].length - 1) {
    solution[x][y] = 1;
    return true;
  }
  if (x < maze.length && y < maze[0].length && maze[x][y] == 1) {
    solution[x][y] = 1;
    if (solveMaze(maze, x + 1, y, solution)) return true;
    if (solveMaze(maze, x, y + 1, solution)) return true;
    solution[x][y] = 0;
    return false;
  }
  return false;
}

medium

A. No base case for destination cell

B. Solution array is not updated correctly

C. Missing check for x and y >= 0 before accessing maze[x][y]

D. Recursive calls do not explore all directions

Solution

1. Step 1: Analyze boundary checks before accessing maze

   The code checks if x < maze.length and y < maze[0].length but does not check if x >= 0 and y >= 0, which can cause ArrayIndexOutOfBoundsException if negative indices occur.

2. Step 2: Verify other parts of the code

   The base case for destination exists, solution array updates correctly, and recursive calls explore down and right directions as expected.

3. Final Answer:

   Missing check for x and y >= 0 before accessing maze[x][y] -> Option C

4. Quick Check:

   Bounds must include >= 0 [OK]

Hint: Always check indices >= 0 and < length before access [OK]

Common Mistakes:

• Ignoring negative index checks
• Assuming base case is missing
• Thinking solution array update is wrong

5. You have a 4x4 maze represented as:

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

If the rat can move in all four directions (up, down, left, right) but cannot visit the same cell twice, which of the following is the correct path the rat can take from (0,0) to (3,3)?

hard

A. [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)]

B. [(0,0), (0,1), (1,1), (2,1), (3,1), (3,2), (3,3)]

C. [(0,0), (1,0), (2,0), (3,0), (3,1), (3,2), (3,3)]

D. [(0,0), (1,0), (1,1), (1,2), (2,2), (3,2), (3,3)]

Solution

1. Step 1: Trace possible path from (0,0) to (3,3) moving up/down/left/right

   Start at (0,0), move down to (1,0), right to (1,1), down to (2,1), down to (3,1), right to (3,2), right to (3,3). All cells are 1 and not visited twice.

2. Step 2: Verify other options for invalid moves or blocked cells

   [(0,0), (0,1), (1,1), (2,1), (3,1), (3,2), (3,3)] moves to (0,1) which is 0 (blocked). [(0,0), (1,0), (2,0), (3,0), (3,1), (3,2), (3,3)] moves to (2,0) which is 0. [(0,0), (1,0), (1,1), (1,2), (2,2), (3,2), (3,3)] moves to (1,2) which is 0. So only [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)] is valid.

3. Final Answer:

   [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)] -> Option A

4. Quick Check:

   Valid path with allowed moves = [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)] [OK]

Hint: Check cell value 1 and no repeats in path [OK]

Common Mistakes:

• Choosing paths through blocked cells (0)
• Revisiting same cell twice
• Ignoring allowed movement directions