HDU 2612 Find a way

题目如下:

圣诞节要到了,坤神和瑞瑞这对基佬想一起去召唤师大峡谷开开车。百度地图一下,发现周围的召唤师大峡谷还不少,这对基佬纠结着,该去哪一个。。。坤神:我要去左边的这个(因为离自己比较近 哈哈~)。。瑞瑞:我要去右边的这个(因为离自己比较近 嘿嘿~) ........这对基佬闹矛盾了,开车有危险了! 为了不让他们去召唤师大峡谷坑人,riot决定让他们去X召唤师大峡谷,保证他俩所走的路程和最短。每走一个点需要花费11分钟,输出他们一共花费多少时间(最短时间噢)


Input

多组测试数据

每组数据,开始一行n,m (2<=n,m<=200)

接下来是个n x m的矩阵

'Y' 表示坤神所在的初始位置

'M' 表示瑞瑞所在的初始位置

'#' 该点禁止通行

'.' 该点可通行

'@' 召唤师大峡谷


Output

每组测试数据,输出坤神和瑞瑞到达同一个召唤师大峡谷所花费的最短时间。

Sample Input

4 4

Y.#@

....

.#..

@..M

4 4

Y.#@

....

.#..

@#.M

5 5

Y..@.

.#...

.#...

@..M.

#...#


Sample Output

66

88

66


Hint

对于第一组样例,坤神和瑞瑞去矩阵(4,1) 这个召唤师大峡谷,耗费的时间为 3 * 11 + 3 * 11 = 66, 去矩阵(1,4)这个召唤师大峡谷,耗费的时间为 5 * 11 + 3 * 11 = 88 。所以,最终答案:66。


解题思路:

这道题是一道双bfs的题目,我们需要先求得以Y为起点,到达所有终点时的最短距离。这样的话,就得需要执行一次bfs。并且,我们还需要求得以M为起点,到达所有终点时的最短距离。一共需要两次bfs。并且,在这道题中终点不止两个,可能会有多个。还存在Y和M都到达不了的终点。最后,我们还需要将Y和M所求得的多个终点的最短距离相加,并从中取得最小距离的终点。不懂的话,就阅读一下代码吧~


注意,这道题中由于图可以到达(200,200)。所以遍历的状态非常多,我们需要用scanf/printf进行输入输出,而不要用cin/cout。不然的话可能会TLS!


并且,这道题你也可以单独写两个以Y为起点的bfs和以M为起点的bfs。但是,这么写的话实现起来比较麻烦,因此不推荐这么写。


代码如下:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct Node
{
	int x, y;
};
struct Node Y, M;
struct Node New;                                      //定义一个移动之后的点new
queue<struct Node> Q;
void bfs(struct Node start);
void init();
bool vis[202][202];         //访问数组
const int INF = 0x3f3f3f3f; //定义极大值
int End[202][202];          //存储每个终点的最终步数(终点的最终步数 = 以Y为起点的bfs后终点步数 + 以M为起点的bfs后终点步数)
int status[202][202];       //存储每个点的步数
char Graph[202][202];       //图
int x[4] = { 1,0,-1,0 };    //方向数组(代表四个方向)
int y[4] = { 0,1,0,-1 };
int n, m;

void bfs(struct Node start)
{
	init();
	int movex, movey;              //代表移动之后的坐标
	int i;
	struct Node temp;              //代表当前正在遍历的顶点
	Q.push(start);                 //起点入队
	vis[start.x][start.y] = true;  //代表起点已经访问过
	status[start.x][start.y] = 0;  //起点距离起点的位置为0
	while (!Q.empty())
	{
		temp = Q.front();
		Q.pop();
		if (Graph[temp.x][temp.y] == '@')                    //如果遍历到了终点
		{
			End[temp.x][temp.y] += status[temp.x][temp.y];   //将终点所需的距离进行累加( 其中 status[temp.x][temp.y]代表当前起点进行bfs时,终点的距离)
		}
		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;                             //代表这个点已经访问
				status[movex][movey] = status[temp.x][temp.y] + 11;   //进行距离的计算
				New.x = movex;                                        //移动之后需更改x坐标
				New.y = movey;                                        //移动之后需更改y坐标
				Q.push(New);                                          //将移动后的坐标进行入队
			}
		}

	}
}

void init()
{
	int i, j;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			vis[i][j] = false;
			status[i][j] = -1;
		}
	}
}

int main()
{
	int i, j;
	int time = INF;
	while (scanf("%d %d", &n, &m) != EOF)
	{
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < m; j++)
			{
				End[i][j] = 0;                    //将终点的最终距离都初始化为0
			}
		}
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < m; j++)
			{
				scanf(" %c", &Graph[i][j]);
				if (Graph[i][j] == 'Y')
				{
					Y.x = i;
					Y.y = j;
				}
				if (Graph[i][j] == 'M')
				{
					M.x = i;
					M.y = j;
				}
			}
		}
		bfs(Y);                                     //以Y为起点进行bfs
		bfs(M);                                     //以M为起点进行bfs
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < m; j++)
			{
				if (Graph[i][j] == '@' && vis[i][j] == true)   //如果此点为终点,且终点是访问过的
				{
					time = min(time, End[i][j]);      //将所有到的终点进行计算,从到的终点中得出最小时间的终点
				}
			}
		}
		printf("%d\n", time);
		time = INF;
	}
}
上一篇:CF2B The least round way


下一篇:Code-Output File-Two Way