Problem D
Ground Is Lava
Minecraft1 Steve is spelunking in a mine when he comes to a room full of lava and stone islands. He wants to jump across the cavern to make it to the opposite side, where he sees a block of diamond ore. He can jump from one block to another if they have no more than $d$ blocks between them; up, down, left, or right. Every time he jumps between blocks, he incurs a risk of falling into the lava. In order to reduce the risk of falling into lava, what is the minimum number of jumps that Steve can make in order to cross the cavern?
Note that Steve starts at the top left corner and the diamond ore is always located at the bottom right corner.
The first three test cases are for the room in the image beneath.
![\includegraphics[width=0.3\textwidth ]{baseworld.png}](/problems/groundislava/file/statement/en/img-0001.png)
The next image shows a path that Steve could take if his jump distance is one. Blue squares show his trail and red squares show where he had to jump.
![\includegraphics[width=0.3\textwidth ]{1jump.png}](/problems/groundislava/file/statement/en/img-0002.png)
The next image shows a path that Steve could take in the same room if his jump distance is two.
![\includegraphics[width=0.3\textwidth ]{2jump.png}](/problems/groundislava/file/statement/en/img-0003.png)
Input
The first line of input contains three space-separated integers; $r$, $c$, and $d$ ($1 \leq r, c \leq 100; 0 \leq d \leq 9$) where $r$ and $c$ are the number of rows and columns of blocks in the cavern floor, respectively, and $d$ is the maximum jump distance. The next $r$ lines contain $c$ space-separated integers, $0$ or $1$, where a $0$ denotes a lava block and a $1$ denotes the ground. The top left and bottom right corners are guaranteed to be a $1$.
Output
Output a single integer representing the minimum number of jumps needed for Steve to arrive at the diamond ore, or $-1$ if no path exists between the said corners.
| Sample Input 1 | Sample Output 1 |
|---|---|
14 15 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 0 1 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
14 15 2 1 1 0 0 0 1 0 1 1 1 1 0 0 1 0 1 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
14 15 3 1 1 0 0 0 1 0 1 1 1 1 0 0 1 0 1 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 |
3 |
Footnotes
- Minecraft, associated characters, and imagery © Mojang. Used here for educational purposes only, in accordance with fair use as defined by section 107 of the Copyright Act.