1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=25;
struct Node{
int a,b,c;
Node *p[4];
Node(int a=0,int b=0,int c=0):a(a),b(b),c(c){}
};
int m,n,k,maze[maxn][maxn];
bool arrived[maxn][maxn];
int run[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
Node* root;
queue<Node*>ept;
queue<queue<Node*> >tree;
Node* newnode(int a,int b,int c){
Node* temp;
temp=new Node(a,b,c);
for(int i=0;i<4;i++)
temp->p[i]=NULL;
return temp;
}
bool inmaze(int a,int b){
if(a>=0&&a<m&&b>=0&&b<n)
return true;
return false;
}
void build(Node* a){
int x=a->a,y=a->b,z=a->c,aa,bb;
if(maze[x][y]) z--;
else z=k;
if(!maze[x][y]||(maze[x][y]&&z==k-1)) arrived[x][y]=true;
for(int i=0;i<4;i++){
aa=x+run[i][0],bb=y+run[i][1];
if(inmaze(aa,bb)&&!arrived[aa][bb]&&(!maze[aa][bb]||z>0)){
a->p[i]=newnode(aa,bb,z);
tree.back().push(a->p[i]);
}
}
return;
}
int main(){
int t;
cin>>t;
while(t--){
int move=0;
cin>>m>>n>>k;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>maze[i][j];
root=newnode(0,0,k);
tree.push(ept);
tree.push(ept);
tree.front().push(root);
while(1){
if(arrived[m-1][n-1]) break;
if(tree.front().empty()&&tree.back().empty()){
move=-1;
break;
}
if(tree.front().empty()){
tree.pop();
tree.push(ept);
move++;
}
build(tree.front().front());
tree.front().pop();
}
cout<<move<<endl;
memset(arrived,0,sizeof(arrived));
memset(maze,0,sizeof(maze));
tree.pop();
tree.pop();
}
return 0;
}
|