BFSパトロールロボット

パトロールロボット
テーマリンク:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83498#problem/F
タイトルの大意:
    ロボットが長方形のエリアをパトロールしているのは、グリッド(m行とn列)です.左上(1,1)から右下(m,n)までです.ネットワーク
の中のいくつかの格子は空地(0で表します)で、その他の格子は障害です(1で表します).ロボットは毎回4つの方向に行きますが、いけません.
連続してk障害を通り抜けて、最も短い長さを求めます.
分析:
 
   bfsで検索しますが、障害があったら記録してください.障害がkを超えたら前のステップに戻ります.

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std;
 5 int n,m,k,t;
 6 int map[25][25];
 7 int d[4][2]= {1,0,-1,0,0,-1,0,1};
 8 int c[25][25][25];
 9 struct A
10 {
11     int x,y;
12     int count;
13     int l;
14     A(int x,int y,int count,int l):x(x),y(y),count(count),l(l) {}
15 };
16 int Do()
17 {
18     queue<A>q;
19     A a(1,1,0,0);
20     q.push(a);
21     c[1][1][0]=1;
22    while(!q.empty())
23     {
24         A now=q.front();
25          q.pop();
26         if(now.x==n&&now.y==m)
27             return now.count;
28         for(int i=0; i<4; i++)
29         {
30             int x=d[i][0]+now.x;
31             int y=d[i][1]+now.y;
32             int l=now.l;
33             if(map[x][y]==1)
34                 l++;
35                 else
36                 l=0;
37             if(l<=k&&c[x][y][l]!=1&&x>=1&&y>=1&&x<=n&&y<=m)
38             {
39                 c[x][y][l]=1;
40                 q.push(A(x,y,now.count+1,l));
41             }
42         }
43     }
44     return -1;
45 }
46 int main()
47 {
48     cin>>t;
49     while(t--)
50     {    
51           memset(c,0,sizeof(c));
52         cin>>n>>m>>k;
53         for(int i=1; i<=n; i++)
54             for(int j=1; j<=m; j++)
55                 cin>>map[i][j];
56         cout<<Do()<<endl;
57     }
58     return 0;
59 }