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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Rat's Path in a Simple Maze

What is the output path of the rat in the maze after running the given Rust code?

DSA Rust

fn rat_in_maze(maze: &Vec<Vec<i32>>, x: usize, y: usize, path: &mut Vec<(usize, usize)>) -> bool {
    let n = maze.len();
    if x == n - 1 && y == n - 1 {
        path.push((x, y));
        return true;
    }
    if x < n && y < n && maze[x][y] == 1 {
        path.push((x, y));
        if rat_in_maze(maze, x + 1, y, path) {
            return true;
        }
        if rat_in_maze(maze, x, y + 1, path) {
            return true;
        }
        path.pop();
    }
    false
}

fn main() {
    let maze = vec![
        vec![1, 0, 0, 0],
        vec![1, 1, 0, 1],
        vec![0, 1, 0, 0],
        vec![1, 1, 1, 1],
    ];
    let mut path = Vec::new();
    if rat_in_maze(&maze, 0, 0, &mut path) {
        for (x, y) in path {
            print!("({},{}) ", x, y);
        }
    } else {
        println!("No path found");
    }
}

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 No path found

D (0,0) (1,0) (1,1) (1,3) (3,3)

💡 Hint

Trace the path by moving down first, then right, only through cells with value 1.

The rat starts at (0,0). It moves down to (1,0), then right to (1,1), down to (2,1), down to (3,1), right to (3,2), and finally right to (3,3). This is the only valid path through cells with value 1.

🧠 Conceptual

intermediate

Understanding Backtracking in Rat in a Maze

Which statement best describes the role of backtracking in the Rat in a Maze problem?

A Backtracking tries all possible paths and remembers the first successful one by undoing wrong moves.

B Backtracking moves only forward without revisiting any cell to find the path.

C Backtracking randomly selects paths until it finds the exit.

D Backtracking uses a queue to explore all paths simultaneously.

💡 Hint

Think about how the algorithm handles dead ends.

Backtracking explores paths and if a path leads to a dead end, it goes back (undoes moves) to try other paths until it finds the exit.

🔧 Debug

advanced

Identify the Error in Maze Boundary Check

What error will occur when running this Rust code for the Rat in a Maze problem?

DSA Rust

fn rat_in_maze(maze: &Vec<Vec<i32>>, x: usize, y: usize, path: &mut Vec<(usize, usize)>) -> bool {
    let n = maze.len();
    if x == n - 1 && y == n - 1 {
        path.push((x, y));
        return true;
    }
    if maze[x][y] == 1 {
        path.push((x, y));
        if rat_in_maze(maze, x + 1, y, path) {
            return true;
        }
        if rat_in_maze(maze, x, y + 1, path) {
            return true;
        }
        path.pop();
    }
    false
}

fn main() {
    let maze = vec![
        vec![1, 0, 0],
        vec![1, 1, 0],
        vec![0, 1, 1],
    ];
    let mut path = Vec::new();
    if rat_in_maze(&maze, 0, 0, &mut path) {
        for (x, y) in path {
            print!("({},{}) ", x, y);
        }
    } else {
        println!("No path found");
    }
}

A No error; code runs correctly and prints the path

B Stack overflow due to infinite recursion

C Compilation error because of missing return statement

D Index out of bounds panic due to missing boundary check before accessing maze[x][y]

💡 Hint

Check if the code verifies x and y are within maze size before accessing maze[x][y].

The code accesses maze[x][y] without checking if x and y are within bounds, which can cause a runtime panic if x or y exceed maze size.

🚀 Application

advanced

Modify Maze to Block a Path

Given the maze below, which modification will block the only path from start (0,0) to end (3,3)?

DSA Rust

let maze = vec![
    vec![1, 0, 0, 0],
    vec![1, 1, 0, 1],
    vec![0, 1, 0, 0],
    vec![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][3] from 1 to 0

💡 Hint

Block a cell that is part of the only valid path.

Changing maze[2][1] to 0 blocks the path at a critical point, making it impossible for the rat to reach the end.

❓ Predict Output

expert

Output of Rat in Maze with Multiple Paths

What is the output path of the rat in the maze after running the given Rust code that explores all paths and returns the first found?

DSA Rust

fn rat_in_maze(maze: &Vec<Vec<i32>>, x: usize, y: usize, path: &mut Vec<(usize, usize)>) -> bool {
    let n = maze.len();
    if x == n - 1 && y == n - 1 {
        path.push((x, y));
        return true;
    }
    if x < n && y < n && maze[x][y] == 1 {
        path.push((x, y));
        if rat_in_maze(maze, x, y + 1, path) {
            return true;
        }
        if rat_in_maze(maze, x + 1, y, path) {
            return true;
        }
        path.pop();
    }
    false
}

fn main() {
    let maze = vec![
        vec![1, 1, 0, 0],
        vec![0, 1, 1, 1],
        vec![0, 0, 0, 1],
        vec![0, 0, 0, 1],
    ];
    let mut path = Vec::new();
    if rat_in_maze(&maze, 0, 0, &mut path) {
        for (x, y) in path {
            print!("({},{}) ", x, y);
        }
    } else {
        println!("No path found");
    }
}

A No path found

B (0,0) (1,0) (1,1) (1,2) (1,3) (2,3) (3,3)

C (0,0) (0,1) (1,1) (1,2) (1,3) (2,3) (3,3)

D (0,0) (0,1) (0,2) (1,2) (1,3) (2,3) (3,3)

💡 Hint

The code tries moving right first, then down.

The rat moves right first from (0,0) to (0,1), then down to (1,1), right to (1,2), right to (1,3), down to (2,3), and down to (3,3).

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 total number of cells 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

   The goal is not counting cells, sorting, or shortest distance but finding a valid path through allowed cells.

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, not counting or sorting [OK]

Common Mistakes:

• Confusing pathfinding with counting cells
• Thinking it finds shortest path always
• Mixing it with sorting or graph distance problems

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

easy

A. fn solve_maze(maze: Vec<i32>, x: usize, y: usize) -> Vec<(usize, usize)>

B. fn solve_maze(maze: Vec, x: i32, y: i32) -> i32

C. fn solve_maze(maze: &mut Vec<i32>, x: usize, y: usize) -> bool

D. fn solve_maze(maze: &Vec, x: usize, y: usize, path: &mut Vec<(usize, usize)>) -> bool

Solution

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

   The maze is a 2D grid, so it should be a reference to a vector of vectors of integers (&Vec). Coordinates are usize for indexing.

2. Step 2: Check return type and path parameter

   The function returns bool to indicate success and uses a mutable path vector to store the route.

3. Final Answer:

   fn solve_maze(maze: &Vec, x: usize, y: usize, path: &mut Vec<(usize, usize)>) -> bool -> Option D

4. Quick Check:

   Correct signature uses references and bool return [OK]

Hint: Use references for maze and bool return for success [OK]

Common Mistakes:

• Passing maze by value causing unnecessary copying
• Using wrong coordinate types (i32 instead of usize)
• Returning wrong types like i32 or Vec instead of bool

3. Given the following Rust code snippet for Rat in a Maze, what will be printed?

fn main() {
    let maze = vec![
        vec![1, 0, 0, 0],
        vec![1, 1, 0, 1],
        vec![0, 1, 0, 0],
        vec![1, 1, 1, 1],
    ];
    let mut path = Vec::new();
    if solve_maze(&maze, 0, 0, &mut path) {
        println!("Path found: {:?}", path);
    } else {
        println!("No path found");
    }
}

fn solve_maze(maze: &Vec, x: usize, y: usize, path: &mut Vec<(usize, usize)>) -> bool {
    let n = maze.len();
    if x == n - 1 && y == n - 1 {
        path.push((x, y));
        return true;
    }
    if x < n && y < n && maze[x][y] == 1 {
        path.push((x, y));
        if x + 1 < n && solve_maze(maze, x + 1, y, path) {
            return true;
        }
        if y + 1 < n && solve_maze(maze, x, y + 1, path) {
            return true;
        }
        path.pop();
    }
    false
}

medium

A. Path found: [(0, 0), (1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)]

B. Path found: [(0, 0), (0, 1), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)]

C. No path found

D. Path found: [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]

Solution

1. Step 1: Trace the recursive calls from (0,0)

   Start at (0,0) which is 1 (allowed). Try moving down to (1,0) which is 1, then (2,0) is 0 (blocked), so backtrack. Then try right from (1,0) to (1,1) which is 1.

2. Step 2: Continue path to destination

   From (1,1), down to (2,1) is 1, then down to (3,1) is 1, right to (3,2) is 1, and right to (3,3) is 1 (destination). Path is [(0,0),(1,0),(1,1),(2,1),(3,1),(3,2),(3,3)].

3. Final Answer:

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

4. Quick Check:

   Recursive path = Path found: [(0, 0), (1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)] [OK]

Hint: Follow down then right moves recursively [OK]

Common Mistakes:

• Assuming path goes right first instead of down
• Not backtracking correctly on blocked cells
• Confusing coordinates order in path

4. Identify the bug in this Rust code snippet for Rat in a Maze and select the fix:

fn solve_maze(maze: &Vec, x: usize, y: usize, path: &mut Vec<(usize, usize)>) -> bool {
    let n = maze.len();
    if x == n - 1 && y == n - 1 {
        path.push((x, y));
        return true;
    }
    if x < n && y < n && maze[x][y] == 1 {
        path.push((x, y));
        if solve_maze(maze, x + 1, y, path) {
            return true;
        }
        if solve_maze(maze, x, y + 1, path) {
            return true;
        }
        path.pop();
    }
    false
}

medium

A. Change maze parameter to mutable reference

B. Remove path.pop() to keep all visited cells

C. Add boundary checks before recursive calls to avoid out-of-bounds

D. Return i32 instead of bool for success

Solution

1. Step 1: Analyze recursive calls for boundary safety

   The recursive calls use x+1 and y+1 without checking if they exceed maze size, risking out-of-bounds panic.

2. Step 2: Fix by adding boundary checks before recursion

   Adding checks like x + 1 < n and y + 1 < n before calling solve_maze prevents invalid indexing.

3. Final Answer:

   Add boundary checks before recursive calls to avoid out-of-bounds -> Option C

4. Quick Check:

   Boundary checks prevent panic [OK]

Hint: Always check indices before recursive calls [OK]

Common Mistakes:

• Ignoring index bounds causing runtime panic
• Changing maze to mutable unnecessarily
• Removing path.pop() causing wrong paths

5. You want to modify the Rat in a Maze solution in Rust to find all possible paths from start to finish instead of just one. Which approach is best?

hard

A. Use a queue to perform breadth-first search and return the shortest path only

B. Return a vector of paths and explore all possible moves recursively without stopping at first success

C. Stop recursion as soon as one path is found to save time

D. Modify the maze to mark visited cells permanently to avoid revisiting

Solution

1. Step 1: Understand requirement to find all paths

   Finding all paths means exploring every possible route without stopping at the first success.

2. Step 2: Use recursion to explore all moves and collect paths

   Return a vector of paths and do not return early. Backtrack properly to explore all options.

3. Final Answer:

   Return a vector of paths and explore all possible moves recursively without stopping at first success -> Option B

4. Quick Check:

   Explore all paths recursively [OK]

Hint: Collect all paths, don't stop at first success [OK]

Common Mistakes:

• Stopping recursion early losing other paths
• Using BFS only for shortest path, not all paths
• Marking visited permanently blocking other paths