Unique paths in a grid with obstacles!

Revision en2, by code_warrior, 2020-06-29 09:36:46

Recently ,I faced a question which says that given a square matrix of size n x n with entries only as 0 ans 1's ,we are required to count the number of unique paths from (1,1) to (n,n) if "0" means that the cell is safe and "1" means that there is an obstacle. We are allowed to move in four directions if possible that is from (X,Y), one can move to (X,Y+1), (X,Y-1),(X+1,Y) or (X-1,Y). Each cell can be visited at most once. I tried to solve it with dyanamic programming , but couldn't make my way to AC. One thing more, N<=20. Can anyone give me some hint how to solve this?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English code_warrior 2020-06-29 09:36:46 22 Tiny change: 'y to AC.\n\nCan anyo' -> 'y to AC.\nOne thing more, N<=20.\nCan anyo'
en1 English code_warrior 2020-06-29 09:30:22 598 Initial revision (published)