1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn = 20 + 5; 7  8 int G[maxn][maxn], vis[maxn][maxn][maxn], d[maxn][maxn]; 9 10 struct Node {11     int x, y, cnt;12 };13 14 const int dx[4] = {0, 0, 1, -1};15 const int dy[4] = {1, -1, 0, 0};16 17 int main() {18     //freopen("slyar.in", "r", stdin);19     //freopen("slyar.out", "w", stdout);20     int T;21     scanf("%d", &T);22     while (T--) {23         int m, n, k;24         scanf("%d%d%d", &m, &n, &k);25         memset(G, 0, sizeof(G));26         for (int i = 1; i <= m; i++)27             for (int j = 1; j <= n; j++)28                 scanf("%d", &G[i][j]);29         memset(vis, 0, sizeof(vis));30         memset(d, -1, sizeof(d));31         d[1][1] = 0; vis[1][1][0] = 1;32         Node t; t.x = 1, t.y = 1, t.cnt = 0;33         queue<Node> q;34         q.push(t);35         while (!q.empty()) {36             Node u = q.front(); q.pop();37             //  printf("x = %d, y = %d, cnt = %d\n", u.x, u.y, u.cnt);38             if (u.x == m && u.y == n) break;39             for (int i = 0; i < 4; i++) {40                 int nx = u.x + dx[i], ny = u.y + dy[i];41                 if (nx >= 1 && nx <= m && ny >= 1 && ny <= n) {42                      if (G[nx][ny] == 1 && u.cnt + 1 > k) continue;43                      Node v = u; v.x = nx, v.y = ny;44                      if (G[nx][ny] == 1) v.cnt++; else v.cnt = 0;45                      if (vis[nx][ny][v.cnt]) continue; else vis[nx][ny][v.cnt] = 1;46                      d[nx][ny] = d[u.x][u.y] + 1;47                      q.push(v);48                 }49             }50         }51         printf("%d\n", d[m][n]);52     }53     return 0;54 }