BFS【古希腊之争（二）】(bfs+优先队列)

题目描述

话说，年轻的斯巴达勇士们终于走出迷宫，取得胜利并顺利赶了回来。可是等他们回到斯巴达的时候才发现，雅典人趁他们不在偷袭了城邦，并抓走了他们的爱人。侥幸逃出来的几个人说，她们被关押在一个迷宫的牢房里，并把关押她们的迷宫里的情况告诉了年轻的勇士：迷宫中的”S”点表示迷宫的入口，”T”点表示迷宫中牢房的位置，”.”表示空地，可以通过，”#”表示墙，不能直接通过，”K”表示陷阱，一旦进入就必死无疑。每次只能向上下左右四个方向移动，每移动一个单位距离需要耗费一个单位时间，所有斯巴达勇士的移动速度相同。

又是迷宫！！！这次斯巴达的勇士们彻底愤怒了！What’s more, today is the ！

由于斯巴达的勇士们无比愤怒，而且她们也想尽可能的在今天就能救出他们的爱人。所以当他们在迷宫中遇到墙的阻碍时，也能破墙进入。不过破墙的过程会花费一个单位的时间。现在请你计算一下他们最短需要多少时间才能找到迷宫的牢房。

PS：假设迷宫中每个点可以容纳的人数没有限制，每个斯巴达勇士的行动方向之间没有影响。

输入格式

每组测试数据第一行输入二个数n,m(2= 0 0表示输入结束，详细输入格式见样例。

输出

输出一个整数，表示找到迷宫出口的最短时间，每组输出占一行。如不能找到出口输入-1

样例输入

3 4

S#.#

..K.

KKT.

0 0

样例输出

8

STL 中优先队列的使用方法()

优先队列容器与队列一样，只能从队尾插入元素，从队首删除元素。但是它有一个特性，就是队列中最大的元素总是位于队首，所以出队时，并非按照先进先出的原则进行，而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了由大互小的顺序排序。元素的比较规则默认按元素值由大到小排序，可以重载“q; //通过操作，按照元素从小到大的顺序出队

2、自定义优先级：

{

()(intx,inty)

{

>y;//x小的优先级高 //也可以写成其他方式，如：[x]>p[y];表示p[i]小的优先级高

}

};

,cmp>q; //定义方法

//其中，第二个参数为容器类型。第三个参数为比较函数。