PK赛 Fire Game（BFS）

http://acm.sdut.edu.cn: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）,布布扣,bubuko.com

PK赛 Fire Game（BFS）

原文：http://blog.csdn.net/u013081425/article/details/21333727