Maze reachability in Rust: memoized down/right search

Determine whether a robot can reach any exit from the upper-left cell of a rectangular room. Open cells contain 0, blocked cells contain 1, and exits contain 2. The robot can move only down or right. It does not move up or left, so this is a directed reachability problem rather than a general four-direction maze search.

Define the state as a cell

Let the answer for (row, column) mean whether an exit is reachable starting there. A position outside the room is false, an exit is true, and a blocked cell is false. An open cell succeeds if either the cell below it or the cell to its right succeeds.

The same cell can be reached by several paths. Without memoization, the recursion repeatedly solves identical suffix regions and can grow exponentially. Store each completed Boolean answer in a memo table. Its entries need three states: unknown, known false, and known true. Treating false as unknown would repeat all unsuccessful searches.

Trace a shared dead end

Consider [[0, 0, 1], [0, 0, 1], [1, 0, 2]]. From the start, moving down or right can eventually reach the center cell. From there the downward route reaches the bottom-middle cell and then the exit. The right neighbor is blocked. Memoizing the center's true result lets a later path reuse it immediately.

Now replace the bottom-middle cell with a wall. The center becomes false. Caching that false is just as useful as caching a success: both incoming paths can stop without exploring the same blocked suffix again. The memo describes reachability from a cell, independent of the path used to arrive there.

Explain why no visiting marker is needed

Every recursive move increases row or column. A path can never return to an earlier cell, so the dependency graph has no cycle. Each state depends only on states farther down or right, and completed answers can be reused safely. General four-direction movement would require a cycle-aware visited policy instead of this argument.

The recurrence checks exactly the legal next moves. If either next state reaches an exit, prefixing the current open cell gives a valid path. If both fail, every legal continuation fails. The out-of-bounds, blocked, and exit base cases complete the correctness argument.

Read the table's absence representation

Java can use boxed Boolean entries so null means unknown. Other languages use optional Booleans, a numeric sentinel, or a map that distinguishes an absent key from a stored false value. The distinction must survive lookup and comparison. A truthiness check alone often collapses unknown and false.

Each of r × c cells has its result computed at most once, with constant work per transition. Time and memo storage are O(r × c). Recursive depth is O(r + c) because a path advances only down and right. The room itself need not be modified. A bottom-up table can remove recursion by processing dependencies from the bottom-right toward the top-left.

Test the movement rule

Use an exit at the start, a blocked start, no exit, a single row, a single column, and a room with several routes to one suffix. Include an arrangement whose only geometric route would require moving left or up; it must fail under this contract. An empty room has no starting cell and returns false.

For an independent oracle, propagate reachable open cells forward from the start and report whether any reachable cell is an exit. This evaluates the directed graph in the opposite direction from the recursive suffix question. A follow-up can count paths, which changes Boolean OR into addition and requires a numeric overflow policy for large rooms.

Rust implementation

Option<bool> stores the tri-state memo explicitly. Shared room slices and mutable memo slices separate read-only input from computed state.

The course supplies any declared node types and invokes the entry in impl Solution, or the design constructor shown here. Owned values move unless borrowed or cloned; the signature makes that choice explicit. An Option separates a missing node or result from a valid value. The runner enables integer overflow checks, so wider constraints require deliberate type and arithmetic changes.

// Open cells are 0
const BLOCKED: i32 = 1;
const EXIT: i32 = 2;

impl Solution {
    pub fn has_exit_path(room_matrix: Vec<Vec<i32>>) -> bool {
        // Return false if the matrix is invalid
        if room_matrix.is_empty() || room_matrix[0].is_empty() {
            return false;
        }

        // Init our memoize matrix: None until we know if a cell is on a path to the exit
        let mut memoized_path_validity = vec![vec![None; room_matrix[0].len()]; room_matrix.len()];

        // Recursively walk through the room to check if there is a valid path
        walk_through_room(&room_matrix, 0, 0, &mut memoized_path_validity)
    }
}

// Recursive helper function
fn walk_through_room(
    room_matrix: &[Vec<i32>],
    row: usize,
    col: usize,
    memo: &mut [Vec<Option<bool>>],
) -> bool {
    // Base case 1: Outside of room, so there can't be a path through this
    let is_outside_room = row >= room_matrix.len() || col >= room_matrix[0].len();
    if is_outside_room {
        return false;
    }

    // Base case 2: A path successfully reached the end, so propagate this upward
    let is_on_valid_path = memo[row][col] == Some(true);
    let is_exit_node = room_matrix[row][col] == EXIT;
    if is_on_valid_path || is_exit_node {
        // Set the current node as true as well
        memo[row][col] = Some(true);
        return true;
    }

    // Base case 3: We reached a blocking node
    let is_on_invalid_path = memo[row][col] == Some(false);
    let is_blocking_node = room_matrix[row][col] == BLOCKED;
    if is_on_invalid_path || is_blocking_node {
        memo[row][col] = Some(false);
        return false;
    }

    // Recursive case: move down and right
    let down_result = walk_through_room(room_matrix, row + 1, col, memo);
    let right_result = walk_through_room(room_matrix, row, col + 1, memo);

    // If both this node's right and down are false, we memoize this to false.
    // If either of the paths are true, we set this node as true since at least one can reach the exit
    memo[row][col] = Some(down_result || right_result);

    // Returns true if either is successful
    down_result || right_result
}

Practice this implementation

Open Robot Maze to run the implementation against the course tests, then change one boundary condition and explain the first failing case. The editor supplies the starter signature and any node types or helper APIs used above. Copy the implementation into that environment; the snippet is the solution body, without the input parser or test driver. Your saved progress belongs to the original lesson.

For more Rust conventions and practice problems, use the Rust interview guide.