fzu2150Fire Game（双起点bfs）

题目链接：http://acm.fzu.edu.cn/problem.php?pid=2150
双起点bfs
“#”是草，可以放两把火，求烧光草的最短时间。
枚举点火的位置，双起点bfs，更新结果。
 1 #include<cstdio>
 2 #include<queue>
 3 #include<cstring>
 4 #include<vector>
 5 using namespace std;
 6 const int inf=0x3f3f3f3f;
 7 char pic[12][12];
 8 int vis[12][12];
 9 int dir[4][2]={0,1,0,-1,1,0,-1,0};
10 int n,m;
11 
12 struct node
13 {
14     int x,y;
15     int d;
16     node(int x,int y,int d):x(x),y(y),d(d){}
17     node(){}
18 }now,nex;
19 
20 int bfs(node s1,node s2)
21 {
22     queue<node>q;
23     while(!q.empty()) q.pop();
24     memset(vis,0,sizeof(vis));
25     vis[s1.x][s1.y]=vis[s2.x][s2.y]=1;
26     q.push(s1);
27     q.push(s2);
28     int sum=inf;
29     while(!q.empty())
30     {
31         now=q.front();
32         q.pop();
33         sum=now.d;
34         for(int i=0;i<4;i++)
35         {
36             nex.x=now.x+dir[i][0];
37             nex.y=now.y+dir[i][1];
38             if(nex.x>=0&&nex.x<n&&nex.y>=0&&nex.y<m&&!vis[nex.x][nex.y]&&pic[nex.x][nex.y]=='#')
39             {
40                 nex.d=now.d+1;
41                 vis[nex.x][nex.y]=1;
42                 q.push(nex);
43             }
44         }
45     }
46     return sum;
47 }
48 int main()
49 {
50     int t;
51     scanf("%d",&t);
52     for(int cas=1;cas<=t;cas++)
53     {
54         int ans=inf;
55         vector<node> v;
56         v.clear();
57         scanf("%d%d",&n,&m);
58         getchar();  //不要忘记吃掉换行符，为此WA-_-||
59         for(int i=0;i<n;i++){
60             for(int j=0;j<m;j++){
61             scanf("%c",&pic[i][j]);
62             if(pic[i][j]=='#')
63             v.push_back(node(i,j,0));
64             }
65             getchar();
66         }
67         for(int i=0;i<v.size();i++)
68             for(int j=i;j<v.size();j++)
69             {
70                 int ok=1;
71                 int temp=bfs(v[i],v[j]);
72                 for(int k=0;k<n;k++)
73                 {
74                     for(int l=0;l<m;l++)
75                     if(vis[k][l]==0&&pic[k][l]=='#')
76                     {
77                         ok=0;
78                         break;
79                     }
80                     if(!ok) break;
81                 }
82                 if(ok&&ans>temp) ans=temp;  //更新最小解
83             }
84         printf("Case %d: ",cas);
85         if(ans==inf) puts("-1");
86         else printf("%d
",ans);
87     }
88 }