front表示当前搜索层，rear表示上一层
d[]表示第几层，b[]表示穿越的障碍数
#include<iostream>
#include<cstring>
#include<set>
#include<cstdio>
#include<queue>
#include<cctype>
using namespace std;
const int M=1000;
int G[25][25],k,x,y;
const int dx[]={0,1,-1,0};
const int dy[]={1,0,0,-1};
set<int> st;
bool inside(int i,int j)
{return i>=0&&i<x&&j>=0&&j<y;
}
bool check(int i,int j)
{int m=i*M+j;if(st.count(m)) return false;return true;
}
void print(int *A)
{for(int i=0;i<50;i++)cout<<A[i]<<' ';cout<<endl;
}
int dfs()
{queue<int> q;q.push(0);int front=1,rear=0;int d[10000]={0},b[10000]={0};while(!q.empty()){
// print(b);
// print(d);
// cout<<endl;int m=q.front();q.pop();int nx=m/M;int ny=m%M;if(ny==y-1&&nx==x-1) return d[rear];for(int i=0;i<4;i++){int gx=nx+dx[i];int gy=ny+dy[i];if(inside(gx,gy)&&check(gx,gy)){if(G[gx][gy]==1){if(b[rear]<k) b[front]=b[rear]+1; //当前穿越障碍数是上一层的+1;else continue;} q.push(gx*M+gy);d[front++]=d[rear]+1; //当前层数是上一层的+1;
// cout<<gx<<' '<<gy<<endl;st.insert(gx*M+gy);}}rear++; //进入下一层;}return -1;
}int main()
{int n;scanf("%d",&n);while(n--){scanf("%d%d%d",&x,&y,&k);memset(G,0,sizeof(G));for(int i=0;i<x;i++)for(int j=0;j<y;j++)scanf("%d",&G[i][j]);st.clear(); st.insert(0);printf("%d\n",dfs());}}