code_warrior's blog

Unique paths in a grid with obstacles!
By code_warrior, history, 4 years ago, In English

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?

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it's will help you

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I just wanted to know what if N<=100000 and the obstacles are less than 3000. How do you solve the problem then? I knew there is a method to iterate only on the obstacles but I forgot that method. Can anyone help?

→ Reply