EmilyBloom's blog

By EmilyBloom, history, 2 months ago, In English

Hi. I recently came accross this question. Link

Given a 2d array where 1 represent a stone and 0 represent water. Return how many path exist in the matrix from top row to the bottom row. You can travel in all directions (top, bottom, left, right) by one position.

Input: [[0, 1, 0, 1, 1],

[0, 1, 1, 0, 1],

[0, 0, 1, 1, 0],

[0, 0, 0, 1, 1]]

The first obvious thought that comes to my mind is backtracking, but that will have large time complexity. How to do this optimally?

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by EmilyBloom (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i guess DP might be the solution

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do the paths have to be simple, i.e. they cannot visit the same entry twice or more?

»
2 months ago, # |
  Vote: I like it -12 Vote: I do not like it

hi, please go to a graph visualizer online and find the number of paths yourself.