单点时限: 2.0 sec
内存限制: 256 MB
一天,sunny 不小心进入了一个迷宫,不仅很难寻找出路,而且有的地方还有怪物,但是 sunny 有足够的能力杀死怪物,但是需要一定的时间,但是 sunny 想早一点走出迷宫,所以请你帮助他计算出最少的时间走出迷宫,输出这个最少时间。
我们规定每走一格需要时间单位 1, 杀死怪物也需要时间 1, 如果不能走到出口,则输出 impossible
. 每次走只能是上下左右 4 个方向。
输入格式
每次首先 2 个数 n,m (0<n,m≤200),代表迷宫的高和宽,然后 n 行,每行 m 个字符。
-
S
代码你现在所在的位置。 -
T
代表迷宫的出口。 -
#
代表墙,你是不能走的。 -
X
代表怪物。 -
.
代表路,可以走。
处理到文件结束。
输出格式
输出最少的时间走出迷宫。不能走出输出 impossible
。
样例
input4 4 S.X. #..# ..#. X..T 4 4 S.X. #..# ..#. X.#Toutput
6 impossible
题意:走迷宫,求最短路径,上下左右走一格花费1,走到有怪的格子花费2.
思路:将每一点的坐标和由起点到该点的距离存入结构体,由起点开始,将该点存入优先队列,以到起点的距离dis为优先级,每次取出dis最小的,向外扩散。
相当于第一轮得出所有到起点距离为1的点,第二轮得出所有到起点距离为2的点。
注意:对普通的最短路问题,由于每个各自的花费相同,因此每次存入的点优先级都相同,故不需要使用优先队列,但本题存在有无怪物的区别,每次存入的格子的优先级可能不同,故使用优先队列。
1 #include<stdio.h> 2 #include<queue> 3 #include<iostream> 4 using namespace std; 5 char maze[201][201]; 6 int sx, sy, tx, ty; 7 //左右上下4个方向 8 int dx[4] = { 1,0,-1,0 }; 9 int dy[4] = { 0,1,0,-1 }; 10 int m, n; 11 struct node { 12 int x, y, dis; 13 }; 14 bool operator < (const node& a, const node& b) 15 { 16 return a.dis > b.dis; 17 } 18 void bfs() { 19 priority_queue<node> que; 20 node st { sx,sy,0 }; 21 maze[sx][sy] = '#'; 22 que.push(st); 23 while (!que.empty()) { 24 node p = que.top(); 25 que.pop(); 26 //若已找到,则退出 27 if (p.x == tx && p.y == ty) { 28 cout << p.dis << endl; 29 return; 30 } 31 for (int i = 0; i < 4; ++i) { 32 int nx = p.x + dx[i]; 33 int ny = p.y + dy[i]; 34 node np{ nx,ny }; 35 if (nx >= 0 && nx < n&&ny >= 0 && ny < m&&maze[nx][ny] != '#') { 36 if (maze[nx][ny] == 'X') 37 np.dis = p.dis + 2; 38 else np.dis = p.dis + 1; 39 maze[np.x][np.y] = '#'; 40 que.push(np); 41 42 } 43 } 44 } 45 printf("impossible\n"); 46 } 47 int main() { 48 while (cin>>n>>m) { 49 for (int i = 0; i < n; i++) 50 scanf("%s", maze[i]); 51 for(int i=0;i<n;i++) 52 for (int j = 0; j < m; j++) 53 { 54 if (maze[i][j] == 'S') 55 sx = i, sy = j; 56 else if (maze[i][j] == 'T') 57 tx = i, ty = j; 58 } 59 bfs(); 60 } 61 return 0; 62 }