FZU 2150 Fire Game

题目如下：

放火烧山

法外狂徒张三在n*m的平地上放火玩，#表示草，张三有分身，他的分身和他本人分别选一个#格子点火，火可以向上向下向左向右在有草的格子蔓延，点火的地方时间为0，蔓延至下一格的时间依次加一。求烧完所有的草需要的最少时间。如不能烧完输出-1。

Input

第一行，输入一个T,表示有T组测试数据。

每组数据由一个n，m分别表示行列

1 <= T <=100, 1 <= n <=10, 1 <= m <=10

Output

输出最少需要的时间>

Sample Input

4

3 3

.#.

.#.

3 3

.#.

#.#

.#.

3 3

...

#.#

...

3 3

..#

#.#

Sample Output

Case 1: 1

Case 2: -1

Case 3: 0

Case 4: 2

解题思路：

这道题首先说的是最短时间，因此这道题我们要用bfs来进行求解。其次在这道题中我们可以将连起来的草当做一个连通块。然后去求连通块的个数，当连通块的个数大于2时，就代表至少有一个连通块无法被烧。（因此导致不能烧完的结果输出-1) 在这道题中有两个起点，起点可以是任意的草(‘#‘)。由于起点不同，因此所花费的时间也会不相同。所以，我们需要遍历所有的起点，从这些起点中寻找燃烧时间最少的进行输出。并且起点可能会有相同的情况。

关于这道题的剪枝处理

如果要输出最短时间的话，则连通块的个数至多为2。由于一个起点在一个连通块当中必然会将连通块烧完。因此当有两个连通块时，我们需要将两个起点只在一个连通块的情况进行剪枝。（因为当有两个连通块时，如果两个起点都在一个连通块中，那么结果肯定是-1。由于有两个起点，两个连通块的情况是一定有结果的。因此，我们不需要这样的无用搜索。只需要搜索两个起点在不同的联通块的情况就可以。)当只有一个连通块时，我们就不需要进行剪枝了。（因为两个起点都只能在一个连通块中，然而这时是一定有结果的)

虽然这道题有两个起点，但是我们可以将这两个起点放在同一个bfs当中进行遍历。（跟之前的bfs的遍历方式没有什么区别) 数连通块的函数，我们可以采用bfs/dfs均可。（数连通块类似于POJ的 Lake Counting 这道题，不懂的话可以去看一下笔记）

Lake Counting 笔记如下： https://www.cnblogs.com/gao79135/p/13979047.html

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <deque>
#include <algorithm>
using namespace std;
int n, m, t;
 struct Point
{
	int x;              //代表每个点的x坐标
	int y;              //代表每个点的y坐标
	int step;           //代表到达该点的步数
	Point() {}          //空构造函数
	Point(int x, int y,int step) : x(x), y(y),step(step) {}         //在这个测试平台中，我们需要加一个构造函数，不然的话就会CE
};
deque<Point> Q;         //定义进行bfs的队列
const int INF = 0x3f3f3f3f;  //定义极大值
char Graph[15][15];     //定义图
int bfs(Point start);   //代表进行bfs的函数
void init();            //代表进行初始化的函数
void find(Point start); //代表找寻连通块的函数
bool vis[15][15];       //代表点的访问状态
int connect[15][15];    //代表点属于哪个连通块
int Count = 0;          //代表联通块数
int x[4] = { 1,0,-1,0 };//代表移动的方向（x坐标）
int y[4] = { 0,1,0,-1 };//代表移动的方向（y坐标）
int sx, sy;             //代表第一个起点
int Time = INF;         //定义最小的时间数

void init()
{
	int i, j;
	for (i = 0; i < 15; i++)
	{
		for (j = 0; j < 15; j++)
		{
			connect[i][j] = 0;           //初始化为0(代表图中的草不属于任何连通块)
		}
	}
}

void find(Point start)                 //在搜索连通块的函数中，每个顶点的step没有任何作用!step是在bfs函数中进行记录最短时间用的
{
	int movex, movey;                    //代表移动之后的坐标
	int i;
	Point temp;                          //代表当前遍历的顶点
	Count++;                             //代表生成的是第Count连通块
	connect[start.x][start.y] = Count;   //代表起点属于第Count个连通块
	Q.push_back(start);                  //将起点进行入队
	while (!Q.empty())
	{
		temp = Q.front();
		Q.pop_front();
		for (i = 0; i < 4; i++)
		{
			movex = temp.x + x[i];
			movey = temp.y + y[i];
			if (movex >= 0 && movex < n && movey >= 0 && movey < m && Graph[movex][movey] == ‘#‘ && connect[movex][movey] == 0)  //代表从当前点找寻下一个不属于任何连通块的点
			{
				Q.push_back(Point(movex,movey,0));//将搜索到的点入队列（由于之前定了一个有参构造函数，因此我们需要将参数传递进构造函数来生成一个结构体，然后再入队列)
				connect[movex][movey] = Count;    //将搜索到的点归属于第Count个连通块中
			}
		}

	}
}

int bfs(Point start)
{
	int i;
	int movex, movey;                           //代表移动之后的坐标
	int Max = -INF;                             //代表整道题所需要的最短时间（因为是以两个起点进行bfs，那么整道题中的最短时间应该取以两个起点进行燃烧的最大时间）
	Point temp;                                 //代表当前正在遍历的顶点
	memset(vis, false, sizeof(vis));            //代表初始化vis数组为false
	Q.push_back(Point(sx,sy,0));                //将第一个起点进行入队
	Q.push_back(Point(start.x,start.y,0));      //将第二个起点进行入队
	vis[sx][sy] = true;                         //第一个/第二个起点均被访问过
	vis[start.x][start.y] = true;  
	while (!Q.empty())
	{
		temp = Q.front();
		Q.pop_front();
		Max = max(Max, temp.step);              //取每个遍历的点的最大时间（取以两个起点进行遍历的最大时间(假设有两个联通块，每个连通块各有一个起点，假设第一个起点燃烧了1秒就结束了，但是第二个起点燃烧了3秒才结束，所以整道题的最小时间应该取3秒)
		for (i = 0; i < 4; i++)
		{
			movex = temp.x + x[i];
			movey = temp.y + y[i];
			if (movex >= 0 && movex < n && movey >= 0 && movey < m && Graph[movex][movey] == ‘#‘ && vis[movex][movey] == false)
			{
				vis[movex][movey] = true;
				Q.push_back(Point(movex,movey,temp.step + 1));
			}
		}

	}
	return Max;
}

int main()
{
	int i, j;                                   //迭代变量i,j
	int k;
	int a, b;                                   //迭代变量a,b
	int sum = 1;                                //代表示例个数
	scanf("%d", &t);
	for (k = 0; k < t; k++)
	{
		init();
		scanf("%d %d", &n, &m);
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < m; j++)
			{
				scanf(" %c", &Graph[i][j]);
			}
		}
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < m; j++)
			{
				if (connect[i][j] == 0 && Graph[i][j] == ‘#‘)   //代表将不属于任何连通块的草为起点进行遍历
				{
					find(Point(i, j, 0));
				}
			}
		}
		if (Count > 2)              //若连通块的数量超过两个，则此题无解。（因为撑死就有两个起点进行bfs遍历，如果出现了2个以上的连通块，则肯定有连通块无法被烧)
		{
			cout << "Case " << sum++ << ": " << -1 << endl;
		}
		else
		{
			for (i = 0; i < n; i++)       //通过循环在连通块中遍历所有的起点情况，并从这些起点遍历所花费的时间中，筛选出最小时间。
			{
				for (j = 0; j < m; j++)
				{
					if (connect[i][j] == 1)          //代表在第一个连通块中寻找起点(并且在连通块中可能会以不同的起点进行遍历，从这些起点中找到最少的燃烧时间)
					{
						sx = i;
						sy = j;
						for (a = 0; a < n; a++)
						{
							for (b = 0; b < m; b++)
							{
								if (connect[a][b] == Count)             //代表在第Count个连通块中寻找起点。（因为Count的个数最多等于2，当图中有两个联通块时，由于上面已经选择了第一个连通块，所以此时Count就一定为2。这样就构成了剪枝效果。如果图中只有一个联通块的话，Count就为1(代表两个起点同时在一个连通块中进行遍历)
								{
									Time = min(Time, bfs(Point(a, b, 0)));    //代表进行bfs搜索并取以不同起点的最短时间（因为在这道题中可以任取‘#‘进行搜索，因此会有不同的起点，由于选择不同的起点，其结果也会不一样，所以我们应该选择花费时间最小的起点)
								}
							}
						}
					}
				}
			}
			cout << "Case " << sum++ << ": " << Time << endl;
		}
		Time = INF;
		Count = 0;
	}
}

FZU 2150 Fire Game

原文：https://www.cnblogs.com/gao79135/p/14113501.html