## uva1600

maksyuki 发表于 oj 分类，标签:

A robot has to patrol around a rectangular area which is in a form of m x 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 (ij) denotes the cell in row iand column j in the grid. At each step, the robot can only move from one cell to an adjacent cell, i.e. from(xy) to (x + 1, y), (xy + 1), (x - 1, y) or (xy - 1). Some of the cells in the grid contain obstacles. In order to move to a cell containing obstacle, the 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 (mn). It is assumed that both these cells do not contain obstacles.

## Input

The input consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each data set, the first line contains two positive integer numbers m and n separated by space (1mn20). The second line contains an integer number k (0k20). The ith line of the next m lines contains ninteger aij separated by space (i = 1, 2,..., m;j = 1, 2,..., n). The value of aij is 1 if there is an obstacle on the cell (ij), and is 0 otherwise.

## Output

For each data set, if there exists a way for the robot to reach the cell (mn), write in one line the integer number s, which is the number of moves the robot has to make; -1 otherwise.

## Sample Input

3 2 5 0 0 1 0 0 0 0 0 0 1 0 4 6 1 0 1 1 0 0 00 0 1 0 1 10 1 1 1 1 00 1 1 1 0 02 2 0 0 1 1 0

7 10 -1