Dsa
Backtracking
Medium
Maize and Corn
In a grid representing a field, some cells contain maize (1) and some cells are empty (0). Your task is to write a program that finds all unique paths from the top-left corner (0,0) to the bottom-right corner (n-1,m-1) of the grid. A valid path can move only down or to the right. Print each unique path as a list of coordinates (x,y) corresponding to each step taken.
Input Format:
- The first line contains two integers n and m, where n is the number of rows and m is the number of columns in the grid (1 ≤ n, m ≤ 10).
- The next n lines each contain m integers (0 or 1) separated by spaces, representing the grid.
Output Format:
- Print each unique path, one per line, as a list of coordinates. If no path exists, print 'No paths found.'
Example:
Input:
3 3
1 0 1
1 1 1
0 1 1
Output:
[(0, 0), (1, 0), (1, 1), (2, 1), (2, 2)]
[(0, 0), (1, 0), (1, 1), (1, 2), (2, 2)]
Key concepts
backtrackingmatricessearch
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