题目如下:
圣诞节要到了,坤神和瑞瑞这对基佬想一起去召唤师大峡谷开开车。百度地图一下,发现周围的召唤师大峡谷还不少,这对基佬纠结着,该去哪一个。。。坤神:我要去左边的这个(因为离自己比较近 哈哈~)。。瑞瑞:我要去右边的这个(因为离自己比较近 嘿嘿~) ........这对基佬闹矛盾了,开车有危险了! 为了不让他们去召唤师大峡谷坑人,riot决定让他们去X召唤师大峡谷,保证他俩所走的路程和最短。每走一个点需要花费11分钟,输出他们一共花费多少时间(最短时间噢)
多组测试数据
每组数据,开始一行n,m (2<=n,m<=200)
接下来是个n x m的矩阵
'Y' 表示坤神所在的初始位置
'M' 表示瑞瑞所在的初始位置
'#' 该点禁止通行
'.' 该点可通行
'@' 召唤师大峡谷
Output
每组测试数据,输出坤神和瑞瑞到达同一个召唤师大峡谷所花费的最短时间。
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;
}
}