Minimum Rolls :
Difficulty Level : Medium
Submissions : 278
Asked In :
Marks :50
: 2 | : 1
You are given a grid of dimension $$$N$$$ * $$$M$$$, where each cell has a number $$$0$$$ or $$$1$$$ on it.$$$0$$$ represents a wall which means you cannot pass through it, and $$$1$$$ means you are free to move. Find the minimum number of rolls required to reach from given source cell to destination cell or report "-1", but condition on rolling is that if you roll , then it continues to roll in the same direction until it gets an edge of grid , or the cell is blocked i.e cell has $$$0$$$ on it.
You can either move right(R), left(L), up(U) or down(D)
The first line contains two space-separated integers $$$1\le N \le 1000$$$ $$$1\le M \le 1000$$$.
Following N lines contains M space separated integers which are either $$$0$$$ or $$$1$$$.
The next line contains two space-separated integers $$$1\le source_{x} \le N$$$ $$$1\le source_{y} \le M$$$
The next line contains two space-separated integers $$$1\le destination_{x} \le N$$$ $$$1\le destination_{y} \le M$$$
Output minimum rolls if possible else output "-1".
5 5 1 1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 5 5
8
5 5 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 5 5
-1
In first test case you have to roll from $$$(1,1)$$$ to $$$(5,5)$$$.
You can move like this $$$RRDDRRDD$$$ for moving from source to target in minimum rolls.
As you can see here after completing $$$4_{th}$$$ roll you have two direction either go $$$L$$$ or $$$R$$$, but chosing $$$R$$$ gives minimum rolls.
