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 }