Rat in a Maze Problem in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rat's Path in a Simple Maze

What is the output path printed by the following Java code for the Rat in a Maze problem?

DSA Java

public class Maze {
    static int N = 4;
    static boolean isSafe(int x, int y, int[][] maze) {
        return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
    }
    static boolean 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(x, y, maze)) {
            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;
    }
    static void solveMaze(int[][] maze) {
        int[][] sol = new int[N][N];
        if (!solveMazeUtil(maze, 0, 0, sol)) {
            System.out.println("No solution");
            return;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(sol[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        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 No solution

C [[1, 0, 0, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

D [[1, 0, 0, 0], [1, 1, 0, 0], [0, 1, 0, 0], [0, 1, 1, 1]]

💡 Hint

Trace the path starting from (0,0) moving only right or down where maze cells are 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 the Movement Constraints

In the Rat in a Maze problem, which of the following movement rules is applied in the provided Java solution?

A The rat can move only right or down to cells with value 1.

B The rat can move in all four directions (up, down, left, right) to any cell.

C The rat can move diagonally and horizontally to cells with value 1.

D The rat can move only left or up to cells with value 1.

💡 Hint

Look at the recursive calls in solveMazeUtil method.

The code tries to move down (x+1, y) first, then right (x, y+1), so only these two directions are allowed.

🔧 Debug

advanced

Identify the Error in Maze Solution Code

What error will occur if the line 'if (sol[x][y] == 1) return false;' is removed from the solveMazeUtil method?

DSA Java

static boolean 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(x, y, maze)) {
        // Removed line: 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;
}

A Compilation error due to missing return statement

B StackOverflowError due to infinite recursion

C No error, code runs correctly

D NullPointerException at runtime

💡 Hint

Consider what happens if the rat revisits the same cell repeatedly.

Without checking if the cell is already part of the solution path, the recursion can cycle infinitely causing stack overflow.

❓ Predict Output

advanced

Output for Maze with No Possible Path

What will be the output of the following Java code when the maze has no path from start to end?

DSA Java

public class Maze {
    static int N = 3;
    static boolean isSafe(int x, int y, int[][] maze) {
        return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
    }
    static boolean 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(x, y, maze)) {
            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;
    }
    static void solveMaze(int[][] maze) {
        int[][] sol = new int[N][N];
        if (!solveMazeUtil(maze, 0, 0, sol)) {
            System.out.println("No solution");
            return;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(sol[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        int[][] maze = {
            {1, 0, 0},
            {0, 0, 0},
            {0, 0, 1}
        };
        solveMaze(maze);
    }
}

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

B [[1,0,0],[0,0,0],[0,0,1]]

C No solution

D ArrayIndexOutOfBoundsException

💡 Hint

Check if the rat can reach the bottom-right corner with given maze.

Since no path exists, the code prints "No solution".

🚀 Application

expert

Number of Unique Paths in a Maze

Given a maze represented by a 2D array where 1 means open cell and 0 means blocked, which approach correctly counts the total number of unique paths from top-left to bottom-right moving only right or down?

A Use recursion with memoization to count paths by exploring right and down moves only on safe cells.

B Use breadth-first search to find the shortest path and count all shortest paths.

C Use a greedy algorithm to always move right if possible, else down.

D Use depth-first search to find one path and multiply by number of open cells.

💡 Hint

Think about counting all possible paths, not just one.

Recursion with memoization efficiently counts all unique paths by avoiding repeated calculations.

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