题目描述
众所周知,duxing哥喜欢吃kfc。
今天终于到了周二,duxing哥又可以去吃kfc了,于是他打开手机app自助点餐,发现附近有许多家kfc店,但是他想选择一家店并尽快取餐回到寝室,忽略到店取餐时间。
地图可以被看做是一个n * m的网格,其中有一些不可通过的障碍,duxing哥、kfc和寝室所在的地方也可以看做是道路,可以通过。duxing哥可以在任意一条道路中选择上下左右四个方向移动,一次移动算作一步。现从duxing初始位置出发,求取到kfc并且回到家的最少步数。
输入
输入包含多个测试用例。
每个测试用例都包括前两个整数n,m。(1<=n,m<=1000)
接下来的n行,每行包含m个字符,表示地图。
‘S’表示duxing哥的初始位置;
‘E’表示寝室的位置;
‘#’表示障碍;
‘.’表示道路;
‘K’表示kfc。
输出
对于每个测试用例输出一行一个整数,duxing哥带上kfc并且回到寝室需要的最少步数。如果无解,请输出“-1”。
样例输入
5 5
S..##
##..K
K..#.
#.#.K
#.K#E
5 5
S..##
##..K
K..#.
#.#.#
#.K#E
5 5
S....
.....
.....
.....
....E
样例输出
8
-1
-1
c++版本1:
由于题目要求必须经过至少一家kfc,因此最短路径就是其中某一个k到起点的最短路径和到终点的最短路径。
可以先bfs起点和终点2次来求得起点和终点到各个k的最短距离,最后加起来求得每个k的总路径,最小的即为答案。
(第一次写bfs,可能代码有些繁琐了
|
|
c++版本2(感谢shn大佬提供的思路):
可以在之前二维数组dis的基础上再添加一维来表示状态(有没有遇到kfc)
bfs状态转移前后都判断一下是否是k即可,而且这样扩充状态能保证bfs在经过kfc的条件下依然还是最短路径
附上大佬的代码
|
|