本文主要是介绍2534: The Hero Rescued The Princess，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
2534: The Hero Rescued The Princess
| Result | TIME Limit | MEMORY Limit | Run Times | AC Times | JUDGE |
|---|---|---|---|---|---|
 | 3s | 65536K | 308 | 92 | Standard |
美丽的公主被关在古老的施了咒语的城堡中，你作为当今世上最勇敢的英雄，决定救出这位美丽的公主。
如果你成功了，最后公主就会嫁给你。当然故事有点俗套，至少如果你把她救出了，我会免费送你一个气球。
但是有很多的英雄去救，如果别人在你之前把公主救了，那么公主可就不属于你了。所以你一定要加快行动，现在就向目标进发吧。
这个城堡的地图由一个（15*30）的字符矩阵构成，我们可以保证矩阵是封闭的。
城堡中有很多的小怪，当然这对于武功高强你的一定不成问题，但你你需要比平时多用一天的时间。
字符有：
'#'，表示城堡的墙，你不可以穿过；
'.'，表示空地，你需要花费一天的时间走过。
'M'，表示此地有怪，你需要两天的时间走过。
'S'，表示你的初始地点
'T'，表示公主的所在地
首行会有一个整数n(n<=10),表示后面有多少个迷宫，每个城堡由（15*30) 的矩阵构成，
每个城堡有且仅有一个S和T，现在你需要设计合适的路线保证总是尽量早的到公主的地方。
如果没有路线可以救出公主，输出-1；
你只能向上，向下，向左或向右走，但不可以斜着走。
Sample input
1 ############################## #.S#.........................# #..#.........................# #...MT.......................# #.#..........................# #............................# #............................# #............................# #............................# #............................# #............................# #............................# #............................# #............................# ##############################
Sample output
6
Problem Source: Keenas
This problem is used for contest: 124
Submit / Problem List / Status / Discuss
这里主要写一下BFS的代码。注意优先级队列用的是小顶堆。
BFS：
#include<cstdio>
#include<queue>
using namespace std;
char map[16][31];
bool vis[16][31];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
bool flag;
int s_x,s_y,e_x,e_y;//初始位置和目标位置
int res;
struct node
{
int x;
int y;
int step;
};
struct cmp//自定义优先级，这个要记住
{
bool operator()(const node&t1,const node&t2)
{
return t1.step>t2.step;
}
};
priority_queue <node,vector<node>,cmp> q;
void bfs(int x,int y)//其他的都和BFS一样了。和之前一个类似1313（类似迷宫）的代码差不多
{
node temp,temp1;
temp.x=x;
temp.y=y;
temp.step=0;
vis[x][y]=true;
q.push(temp);
while(!q.empty())
{
temp1=q.top();//优先级队列队顶的元素用top！！
q.pop();
if(temp1.x==e_x&&temp1.y==e_y)
{
flag=true;
res=temp1.step;
break;
}
else
{
for(int i=0;i<4;i++)
{
int fx=temp1.x+dx[i];
int fy=temp1.y+dy[i];
if(fx>=0&&fx<15&&fy>=0&&fy<30&&map[fx][fy]!='#'&&!vis[fx][fy])
{
vis[fx][fy]=true;
temp.x=fx;
temp.y=fy;
if(map[fx][fy]=='M')//可以写一起了。使用优先级队列
temp.step=temp1.step+2;
else
temp.step=temp1.step+1;
q.push(temp);
}
}
}
}
}
int main()
{
int n;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&n);
while(n--)
{
while(!q.empty())
{
q.pop();
}
res=0;
flag=false;
for(int i=0;i<15;i++)
for(int j=0;j<30;j++)
{
scanf(" %c",&map[i][j]);
vis[i][j]=false;
if(map[i][j]=='S')
{
s_x=i;
s_y=j;
}
if(map[i][j]=='T')
{
e_x=i;
e_y=j;
}
}
bfs(s_x,s_y);
if(flag)
printf("%d\n",res);
else
printf("-1\n");
}
return 0;
}
*/
#include<stdio.h>
#define MAX 1000;
int visit[15][30],hav,mini;
int map[15][30];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
void dfs(int x,int y,int time)
{
int i;
visit[x][y]=time;
if(time>mini)
return;
if(map[x][y]=='T')
{ if(time<mini)
{
mini=time;
hav=1;
}
return;
}
for(i=0;i<4;i++)
{
if(map[x+dx[i]][y+dy[i]]=='#')continue;
if(map[x+dx[i]][y+dy[i]]=='M')
{
if(visit[x+dx[i]][y+dy[i]]>time+2)
dfs(x+dx[i],y+dy[i],time+2);
}
else
{ if(visit[x+dx[i]][y+dy[i]]>time+1)
dfs(x+dx[i],y+dy[i],time+1);
}
}
}
int main()
{
int n,i,j,posx,posy;
scanf("%d",&n);
getchar();
while(n--)
{
for(i=0;i<15;i++)
{
for(j=0;j<30;j++)
{
visit[i][j]=MAX;
map[i][j]=getchar();
if(map[i][j]=='S')
{
posx=i;posy=j;
}
}
getchar();
}
hav=0;mini=MAX;
dfs(posx,posy,0);
printf("%d\n",hav?mini:-1);
}
return 0;
}
这篇关于2534: The Hero Rescued The Princess的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
![2534. 乘方 [CSP-J 2022]](https://i-blog.csdnimg.cn/direct/4a5c1d445dc54867a60c0f36ca2eccf2.png)
