980. Robot

Robot has to patrol around a rectangular area which is in a form of `m\ times\ n` grid (`m` rows and `n` columns). The rows are labeled from 1 to `m`. The columns are labeled from 1 to `n`. A cell `(i,\ j)` denotes the cell in row `i` and column `j` in the grid. At each step, the robot can only move from one cell to an adjacent cell, i.e. from `(x,\ y)` to `(x+1,\ y)`, `(x,\ y+1)`, `(x-1,\ y)` or `(x,\ y-1)`. Some of the cells in the grid contain obstacles. In order to move to a cell containing obstacle, robot has to switch to turbo mode. Therefore, the robot cannot move continuously to more than `k` cells containing obstacles.

Your task is to write a program to find the shortest path (with the minimum number of cells) from cell `(1,\ 1)` to cell `(m,\ n)`. It is assumed that both the cells do not contain obstacles.

The first line contains three positive integers `m`, `n` and `k` (`1\ ≤\ m,\ n\ ≤\ 100`, `0\ ≤\ k\ ≤\ 100`). The `i`-th line of the next `m` lines contains `n` integer `a_{ij}` separated by space (`i\ =\ 1,\ 2,\ …,\ m`; `j\ =\ 1,\ 2,\ …,\ n`). The value of `a_{ij}` is 1 if there is an obstacle on the cell `(i,\ j)`, and is 0 otherwise.

If there exists a way for the robot to reach the cell `(m,\ n)`, write the number of moves the robot has to make; `-1` otherwise.

2 5 0
0 1 0 0 0
0 0 0 1 0

7

4 6 1
0 1 1 0 0 0
0 0 1 0 1 1
0 1 1 1 1 0
0 1 1 1 0 0

10

2 2 0
0 1
1 0

-1