PK賽 Fire Game（BFS）

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=99#problem/K

請先允許我表達一下憤懑的心情。周日，天氣晴朗，陽光燦爛，多麼美好的一天。早晨突然病倒了，頭暈的厲害，天轉地轉。中午好不容易起了床，打算下午好好享受一下難得的好天氣。結果下午竟然有比賽，而且我在最後二十分鐘來到實驗室，狂敲了兩個水題結束了。這麼一天就這麼結束了。我發誓以後不管有木有比賽我都堅守在實驗室裡，我那可憐的排名啊。。。

切入正題，有一個n*m的格子，每個格子要麼是草地要麼是空地。有兩個小朋友，他們分別選兩塊草地點燃，只能選一次。點燃一塊草地，下一秒它臨近的草地也會被點燃。問所有格子中的草地被點燃花的最少時間。

思路：枚舉兩塊草地，BFS即可。不過這有個坑點，當只有一塊草地時，直接輸出“0”。以後做題還是要想的全面一點。

#include 
#include 
#include 
#include 
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  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;
}