Robot Maze

You are training a robot to walk through a room to search for an exit. The room will be represented as a matrix. The robot will always start at the top-left at point (0, 0) and can only walk down or right.

There may or may not be a path to the exit in the room. An open node is represented by 0, a blocked node is represented by 1, and an exit is represented by 2.

Write a function hasExitPath that returns a boolean if there is a path to an exit or not.

Breakdown

Approach and test strategy

Reachability in a grid with a restricted move set

Read the approach, boundary cases, and complexity

The board marks open cells with zero, blocked cells with one, and an exit with two. Start at the top-left cell (0, 0) and move only down or right. Do not add diagonal or backward moves from a different maze problem. Reject blocked and out-of-bounds positions before exploring further, and retain repeated-state information when several move sequences can reach the same cell.

Cases to check

Empty boards and empty rows have no exit path.
Try a blocked starting route and an exit separated by walls.
Use an open board with several ways to reach the same cell and verify the algorithm avoids repeated subproblem work.

Cost model

With each permitted grid state processed once, a board with r rows and c columns takes O(r · c) work and at most O(r · c) retained visited or memoized state. A naive branching search can repeat work.

Programming languages for this lesson

Starter code and reference implementations are available in:

The editor shows which of these languages can run on this deployment.

Follow teacher

Table of Contents

Validate My Answer

There can be many paths. We only care if at least one reaches the exit, and then we can return true.
If you solve this recursively, you may be performing a lot of duplicate work. Try to remove these repeated operations to improve your time complexity.
You can solve this in O(r x c) time and space, where r is the number of rows and c is the number of columns.

Follow teacher

Table of Contents

Test Results

Run your code and see results here...

/**
 * @param {List[List[int]]} roomMatrix
 * @return {bool}
 */
function hasExitPath(roomMatrix) {
  // Your solution here
};

Robot Maze

There may or may not be a path to the exit in the room. An open node is represented by 0, a blocked node is represented by 1, and an exit is represented by 2.

Write a function hasExitPath that returns a boolean if there is a path to an exit or not.

/**
 * @param {List[List[int]]} roomMatrix
 * @return {bool}
 */
function hasExitPath(roomMatrix) {
  // Your solution here
};