3029 - 古希腊之争（二）
话说，年轻的斯巴达勇士们终于走出迷宫，取得胜利并顺利赶了回来。可是等他们回到斯巴达的时候才发现，雅典人趁他们不在偷袭了城邦，并抓走了他们的爱人。侥幸逃出来的几个人说，她们被关押在一个迷宫的牢房里，并把关押她们的迷宫里的情况告诉了年轻的勇士：迷宫中的”S”点表示迷宫的入口，”T”点表示迷宫中牢房的位置，”.”表示空地，可以通过，”#”表示墙，不能直接通过，”K”表示陷阱，一旦进入就必死无疑。每次只能向上下左右四个方向移动，每移动一个单位距离需要耗费一个单位时间，所有斯巴达勇士的移动速度相同。
又是迷宫！！！这次斯巴达的勇士们彻底愤怒了！What’s more, today is the Magpie Festival！
由于斯巴达的勇士们无比愤怒，而且她们也想尽可能的在今天就能救出他们的爱人。所以当他们在迷宫中遇到墙的阻碍时，也能破墙进入。不过破墙的过程会花费一个单位的时间。现在请你计算一下他们最短需要多少时间才能找到迷宫的牢房。
PS：假设迷宫中每个点可以容纳的人数没有限制，每个斯巴达勇士的行动方向之间没有影响。
Input
每组测试数据第一行输入二个数n,m(2=<m<=n<=100)分别代表迷宫的长度和宽度。下面n行每行有m个字符用来表示迷宫地图。
0 0表示输入结束，详细输入格式见样例。
Output
输出一个整数，表示找到迷宫出口的最短时间，每组输出占一行。如不能找到出口输入-1
Examples
Input
3 4 S#.# ..K. KKT. 0 0
Output
8
Solution C++
#include <algorithm> #include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; const int N = 300 + 5; struct Coord { int x,y,c; friend bool operator <(const Coord &s1,const Coord &s2) { return s1.c>s2.c; } }; int n, m, sx, sy, ex, ey, vis[N][N], dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; char maze[N][N]; int bfs(int x, int y) { priority_queue <Coord> q; Coord a, t; a.x = x; a.y = y; a.c = 0; q.push(a); vis[x][y] = 1; while (!q.empty()) { a = q.top(); q.pop(); if(a.x == ex && a.y == ey) return a.c; for(int i = 0; i < 4; ++i) { t.x = a.x + dir[i][0]; t.y = a.y + dir[i][1]; if(t.x >= 0 && t.x < n && t.y >= 0 && t.y < m && !vis[t.x][t.y] && maze[t.x][t.y] != 'K') { vis[t.x][t.y] = 1; if(maze[t.x][t.y] == '#') t.c = a.c + 2; if(maze[t.x][t.y] == '.' ||maze[t.x][t.y] == 'T') t.c = a.c + 1; q.push(t); } } } return -1; } int main() { while (cin >> n >> m, m + n) { memset(vis, 0, sizeof(vis)); for(int i = 0; i < n; ++i) { cin >> maze[i]; for(int j = 0; j < m; ++j) { if(maze[i][j] == 'S') { sx = i; sy = j; } if(maze[i][j] == 'T') { ex = i; ey = j; } } } cout << bfs(sx, sy) << endl; } return 0; }