Hi. I recently came accross this question. [Link](https://leetcode.com/discuss/interview-question/2191439/Google-or-Phone-or-Check-if-path-exists)↵
↵
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?↵
↵
↵
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?↵
↵