Problem C: 暴躁机器人

Problem C: 暴躁机器人

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 340  Solved: 115
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI发明了一个暴躁机器人,机器人位于一个 n*m 的网格中, 网格中的一些格子是空地(数字0表示),另一些是障碍物(数字1表示),暴躁机器人从左上角(1,1)出发前往右下角(n,m), 机器人每一步可以往上下左右四个方向走一个,由于机器人很暴躁,所以它可以摧毁障碍物(障碍物摧毁后会重建)。但是它最多连续穿过k 个障碍物,求机器人从左上角到右下角的最短路长度。 保证起点和终点是空地。

Input

输入包含一个正整数T,代表测试用例个数。
对于每组测试用例,第一行包含三个整数 n,m,k (1<=n,m<=20, 0<=k <=20)。
接下来包含一个 n*m 的01矩阵,代表网格矩阵。

Output

对于每组测试用例,输出机器人从左上角走到右下角的最少步数。若无法到达右下角,输出 -1 。

Sample Input

1
3 6 1
0 1 1 0 0 0
0 0 1 0 1 1
0 1 1 1 1 0

Sample Output

9

HINT

测试用例的走法: (1,1) -> (2,1) -> (2,2) -> (2,3) ->(2,4) -> (1,4) -> (1,5) -> (1,6) -> (2,6) -> (3,6) . 路径长度为 9.