Rat in a Maze Problem in DSA C - 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 (usually top-left) to the destination (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 1 usually represent?

A cell with value 1 represents a safe or open path where the rat can move.

intermediate

Why do we mark cells as visited during the Rat in a Maze backtracking process?

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

advanced

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

O(2^(N^2)) in the worst case, because each cell can be either visited or not, leading to exponential possibilities.

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

A Left and Up

B Right and Down

C Diagonal moves only

D All eight directions

Usually, the rat can move only right or down to simplify the problem.

What does a cell value of 0 represent in the maze grid?

A Start position

B Safe path

C Blocked or unsafe path

D Destination

A cell with value 0 means the rat cannot move through it.

Which data structure is most useful to implement backtracking in Rat in a Maze?

A Stack or recursion call stack

B Hash Map

C Queue

D Linked List

Backtracking uses recursion which internally uses a call stack or an explicit stack.

If no path exists in the maze, what should the algorithm return?

A A random path

B The start position only

C The entire maze

D An empty path or false

If no path is found, the algorithm should indicate failure by returning false or an empty path.

What is the first step in the Rat in a Maze backtracking algorithm?

A Check if current cell is destination

B Mark current cell as visited

C Move right

D Move down

The algorithm first checks if the current cell is the destination before moving.

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

Think about trying paths and undoing moves when stuck.

Describe how you would represent the maze and the path in code for the Rat in a Maze problem.

Focus on grid representation and tracking the path.