Rat in a Maze Problem in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Rat in a Maze problem?

To find a path from the start point (usually top-left) to the destination point (usually bottom-right) in a maze represented by a grid, moving only through allowed cells.

beginner

Which algorithmic technique is commonly used to solve the Rat in a Maze problem?

Backtracking, which tries possible paths and backtracks when a path leads to a dead end.

beginner

In the Rat in a Maze problem, what does a cell value of 0 usually represent?

A blocked cell or wall where the rat cannot move.

intermediate

What is the purpose of marking cells as visited in the Rat in a Maze problem?

To avoid revisiting the same cell and getting stuck in infinite loops during the search.

intermediate

How do you represent the path found by the rat in the maze after solving the problem?

Usually by a matrix or grid of the same size where cells on the path are marked (e.g., with 1) and others are 0, showing the route from start to finish.

In the Rat in a Maze problem, which move directions are typically allowed?

A All eight directions

B Left and Up

C Diagonal only

D Up, down, left, right

The rat typically moves in four directions: up, down, left, right.

What does backtracking do when it hits a dead end in the maze?

A Marks the path as successful

B Stops the search completely

C Returns to the previous cell to try a different path

D Moves diagonally

Backtracking returns to the previous cell to explore other possible paths.

What data structure is commonly used to store the maze in the Rat in a Maze problem?

A Linked list

B Array or matrix

C Stack

D Queue

A 2D array or matrix is used to represent the maze grid.

If the maze is represented by a matrix, what does a cell value of 1 usually mean?

A Open cell where the rat can move

B Start point

C Blocked cell

D End point

1 usually means the cell is open and accessible.

What is the time complexity of the Rat in a Maze problem using backtracking for an N x N maze?

A O(2^(N^2))

B O(N^2)

C O(N!)

D O(N)

Backtracking explores all possible paths, which can be exponential in the number of cells.

Explain how backtracking helps solve the Rat in a Maze problem step-by-step.

Think of exploring paths and undoing moves when stuck.

Describe how you would represent the maze and the path solution in code.

Focus on data structures and marking the route.