Dsa
Backtracking
Hard
Historical Pathways
You are given an m x n grid representing a historical map where certain cells are blocked (represented by 1) and the rest are open (represented by 0). You start at the top left corner of the grid and need to find all unique paths to the bottom right corner. Each path can only move down or right, and you must return all unique paths in lexicographically sorted order. If no path exists, return "No valid paths".
Input Format:
- The first line contains two integers m and n (1 ≤ m, n ≤ 10).
- The following m lines contain n integers each representing the grid (0 for open cell, 1 for blocked cell).
Output Format:
- Print each unique path as a string of coordinates (e.g., "(0,0) -> (0,1) -> (1,1)"). If no valid paths exist, print "No valid paths".
Example:
Input:
2 2
0 0
0 0
Output:
(0,0) -> (0,1) -> (1,1)
Key concepts
backtrackingpath findinggrid
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now