PK赛 Fire Game（BFS）

admin管理员组

文章数量:1516870

PK赛 Fire Game（BFS）

:8080/vjudge/contest/view.action?cid=99#problem/K

请先允许我表达一下愤懑的心情。周日，天气晴朗，阳光灿烂，多么美好的一天。早晨突然病倒了，头晕的厉害，天转地转。中午好不容易起了床，打算下午好好享受一下难得的好天气。结果下午竟然有比赛，而且我在最后二十分钟来到实验室，狂敲了两个水题结束了。这么一天就这么结束了。我发誓以后不管有木有比赛我都坚守在实验室里，我那可怜的排名啊。。。

切入正题，有一个n*m的格子，每个格子要么是草地要么是空地。有两个小朋友，他们分别选两块草地点燃，只能选一次。点燃一块草地，下一秒它临近的草地也会被点燃。问所有格子中的草地被点燃花的最少时间。

思路：枚举两块草地，BFS即可。不过这有个坑点，当只有一块草地时，直接输出“0”。以后做题还是要想的全面一点。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;const int INF = 0x3f3f3f3f;
int n,m;
char map[15][15];struct node
{int x;int y;int id;int step;
}p[110];
int cnt;
queue <struct node> que;int bfs(int s1, int s2)
{int vis[110];int ans = -1;while(!que.empty()) que.pop();memset(vis,0,sizeof(vis));vis[s1] = 1;vis[s2] = 1;que.push((struct node) {p[s1].x, p[s1].y, p[s1].id, 0});que.push((struct node) {p[s2].x, p[s2].y, p[s2].id, 0});while(!que.empty()){struct node u = que.front();que.pop();int step = u.step;int i = u.x;int j = u.y;int id;if(ans < step) ans = step;if(map[i][j-1] != '.' && !vis[ u.id -1 ]){vis[u.id - 1] = 1;que.push((struct node) {p[u.id-1].x, p[u.id-1].y, p[u.id-1].id,step+1});}if(map[i][j+1] != '.' && !vis[ u.id+1 ]){vis[u.id+1] = 1;que.push( (struct node) {p[u.id+1].x, p[u.id+1].y, p[u.id+1].id,step+1});}if(map[i-1][j] != '.'){for(int k = 1; k <= cnt; k++){if(p[k].x == i-1 && p[k].y == j){id = p[k].id;break;}}if(!vis[id]){vis[id] = 1;que.push((struct node) {p[id].x, p[id].y, p[id].id, step+1} );}}if(map[i+1][j] != '.'){for(int k = 1; k <= cnt; k++){if(p[k].x == i+1 && p[k].y == j){id = p[k].id;break;}}if(!vis[id]){vis[id] = 1;que.push((struct node) {p[id].x, p[id].y, p[id].id, step+1} );}}}for(int k = 1; k <= cnt; k++){if(vis[k] == 0){ans = -1;break;}}return ans;
}int main()
{int test;scanf("%d",&test);for(int item = 1; item <= test; item++){scanf("%d %d",&n,&m);cnt = 0;for(int i = 1; i <= n; i++){scanf("%s",map[i]+1);for(int j = 1; j <= m; j++)if(map[i][j] == '#')p[++cnt] = (struct node){i,j,cnt};}for(int i = 0; i <= n+1; i++){map[i][0] = '.';map[i][m+1] = '.';}for(int i = 0; i <= m+1; i++){map[0][i] = '.';map[n+1][i] = '.';}if(cnt == 1)		//只有一块草地时{printf("Case %d: 0\n",item);continue;}int tmp,ans = INF;for(int i = 1; i <= cnt-1; i++){for(int j = i+1; j <= cnt; j++){tmp = bfs(i,j);	//枚举两块草地if(tmp != -1 && ans > tmp)ans = tmp;}}printf("Case %d: ",item);if(ans == INF)printf("-1\n");else printf("%d\n",ans);}return 0;
}

本文标签： PK赛 Fire Game（BFS）