I recently gave an online challenge in which the following question was asked,I was able to pass only 1 test case,just wanted to have some guidance on what would be the right approach for it.

Question: There is grid given of NxM. Each cell value represents a value P,which denotes the number of parking spaces available in that city. A person wants to take his vehicle from city C(1,1) to city C(N,M) such that he parks his vehicle at one of the available parking spaces in any city and then he takes a taxi via which he reaches city C(N,M).He can park his vehicle in any city. We have to output the number of ways in which he can reach his destination.

the first line contains N,M.

In each of N lines,M numbers follow.

sample input:

2 2

1 2

0 1

sample output: 3

I tried to use BFS but that gave wrong answers in every case except 1.Please suggest what should be the approach for this question? Thanks.