PPractick

The problem

A robot vacuum maps a square room as an n × n grid: 1 is a free tile and 0 is furniture. It starts at the top-left tile and must reach the charging dock at the bottom-right, moving Down, Left, Right or Up one tile at a time and never revisiting a tile on the same trip. The planning screen should list every possible route as a string of moves (like DRDDRR), in lexicographic order. Backtracking explores moves in alphabetical order (D, L, R, U), marks tiles on the current path, and unmarks them when backing out.

Example: maze 1000 / 1101 / 1100 / 0111 → DDRDRR DRDDRR.

Function signature

vector<string> findPaths(const vector<vector<int>>& maze);  // sorted; empty if unreachable

Test cases

Input maze (rows)	Output	Explanation
1000 / 1101 / 1100 / 0111	DDRDRR DRDDRR
10 / 10	(none)	The destination is blocked
11 / 11	DR RD
01 / 11	(none)	The start is blocked
111 / 101 / 111	DDRR RRDD	Two ways around the centre

(Confirm: moves are D, L, R, U only; a tile can't be revisited on one path; if the start or destination is 0, return no paths.)

How interviewers phrase it

• "Find all possible paths the rat can take from (0, 0) to (n−1, n−1), in lexicographically increasing order" (GeeksforGeeks "Rat in a Maze Problem").

Clarifying questions to ask

1. Which moves are allowed? (Down, Left, Right, Up.)
2. Can a cell be revisited on the same path? (No.)
3. Must the output be sorted?

Follow-ups to expect

1. "How do you get sorted output without sorting?"
2. "Why unmark on the way back?"
3. "Complexity?"
4. "Shortest path only?"
5. "How can you avoid a separate visited array?"

Related questions

• Word Search Hard
• Letter Combinations of a Phone Number Hard
• Palindrome partitioning Hard
• N Queen Hard
• M Coloring Problem Hard
• Sudoku Solver Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in