XYNUOJ1359: 古希腊之争(二) 搜索 BFS 优先队列

xiaoxiao2021-02-28  14

题目描述

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

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

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

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

输入

每组测试数据第一行输入二个数n,m(2=<m<=n<=100)分别代表迷宫的长度和宽度。下面n行每行有m个字符用来表示迷宫地图。

0 0表示输入结束,详细输入格式见样例。

输出

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

样例输入

3 4S#.#..K.KKT.0 0

样例输出

8

#include<stdio.h> #include<string.h> #include<queue> #include <algorithm> using namespace std; int n,m; char map[105][105]; int vis[105][105]; int xdir[4]={0,0,1,-1};//4个方向 int ydir[4]={1,-1,0,0}; int sx,sy,tx,ty; struct node { int x,y,c; friend bool operator <(const node &s1,const node &s2) { //重载 node 类型变量的<运算符。 return s1.c>s2.c; //如果 s1.c>s2.c 则认为 s1<s2。 } //即:s1 在优先队列中的重要性低。 }; int bfs(int x, int y) { priority_queue <node> q; //元素为结构体的优先队列 node 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 == tx && a.y == ty) //到达终点 return a.c; for(int i=0;i<4;i++) { t.x = a.x + xdir[i]; t.y = a.y + ydir[i]; if(t.x > 0 && t.x <= n && t.y > 0 && t.y <= m && !vis[t.x][t.y] && map[t.x][t.y] != 'K') { vis[t.x][t.y] = 1; if(map[t.x][t.y] == '#') t.c = a.c + 2; if(map[t.x][t.y] == '.' ||map[t.x][t.y] == 'T') t.c = a.c + 1; q.push(t); } } } return -1; } int main() { while(scanf("%d%d",&n,&m)!=EOF&&n+m) { memset(vis, 0, sizeof(vis)); for(int i=1;i<=n;i++) { getchar();//吸收换行符 for(int j=1;j<=m;j++) { scanf("%c",&map[i][j]); if(map[i][j]=='S') sx=i,sy=j; if(map[i][j]=='T') tx=i,ty=j; } } printf("%d\n",bfs(sx,sy)); } return 0; }

转载请注明原文地址: https://www.6miu.com/read-2000071.html

最新回复(0)