BFS/DP on a grid

Revision en5, by ss_96, 2017-09-14 13:07:39

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.

Tags c++, graph, dp, bfs


  Rev. Lang. By When Δ Comment
en5 English ss_96 2017-09-14 13:07:39 2 Tiny change: 'e input:\n2 2\n\n1' -> 'e input:\n\n2 2\n\n1'
en4 English ss_96 2017-09-14 13:07:25 4 Tiny change: 'ut:\n2 2\n1 2\n0 1\n\ns' -> 'ut:\n2 2\n\n1 2\n\n0 1\n\ns'
en3 English ss_96 2017-09-14 13:06:43 8
en2 English ss_96 2017-09-14 13:05:45 10
en1 English ss_96 2017-09-14 13:05:19 928 Initial revision (published)