5.5 Ryn Blackwood’s Adventure: Escape
Finally finding the hidden treasure in Viserna, Ryn Blackwood now faces the hardest part — getting out alive. She is given a map to escape in the form of a n x m grid where,
- 0 represents a safe tile and
- 1 represents an unsafe tile
Ryn can only walk on the safe tiles.
Ryn starts at the top-left corner and her goal is to reach the bottom-right corner.
She can move only up, down, left, right to an adjacent safe tile.
However, Ryn has a special ability:
She can make at most k magical hops.
A hop allows her to jump over exactly one adjacent unsafe tile and land on the next tile in the same direction, provided that landing tile is safe.
Ryn wants to know the minimum number of tiles she must visit (including the start and end) to escape.
The tile she hops over is not counted.
If it is impossible to escape, print -1.
Constraints
1 ≤ n, m ≤ 100
0 ≤ k ≤ 10
Grid values: 0 (safe), 1 (unsafe)
Input Format
The first line contains n, m and k where n and k are the dimensions of the gridand k is the maximum number of hops Ryn can do.
The next n lines contains the n x m map grid
Output Format
The minimum number of tiles Ryn must visit (including the start and end) to escape.
If it is impossible to escape, print -1
Example 1
Input:
3 4 1
0 1 0 0
0 1 1 0
0 0 0 0
Output:
5
Explanation:
Direct path is blocked so Ryn uses 1 hop from (0,0) to jump over (0,1) and land on (0,2).
Path: (0,0) → (0,2) → (0,3) → (1,3) → (2,3) = 5 cells.
Log In to solve the Question