A39864. 打怪救公主公主被魔王抓起来关在了迷宫的某处，骑士想要拯救公主，也进入了迷宫。但是魔王不会轻易让骑士拯救公主，魔王在迷宫中安排了许多怪兽。每个怪兽都有血量，骑士也有初始血量，骑士打败怪兽后血量的减少量为怪物的血量值，血量减到0，骑士会死去。迷宫由m*n个方块组成，每个方块有墙或者路或者怪物，骑士在其中一个方块上，他每个时间单位可以四个方向（上、下、左、右）走到相邻方格，若遇到怪物，必须打败怪物才能…
填空题
困难
知识点
题目描述
打怪救公主
公主被魔王抓起来关在了迷宫的某处，骑士想要拯救公主，也进入了迷宫。
但是魔王不会轻易让骑士拯救公主，魔王在迷宫中安排了许多怪兽。
每个怪兽都有血量，骑士也有初始血量，骑士打败怪兽后血量的减少量为怪物的血量值，血量减到0，骑士会死去。
迷宫由m*n个方块组成，每个方块有墙或者路或者怪物，骑士在其中一个方块上，他每个时间单位可以四个方向（上、下、左、右）走到相邻方格，若遇到怪物，必须打败怪物才能继续前进。
请帮忙判断骑士能否成功拯救公主，如果能，给出骑士还剩的最大血量。
输入
第一行为三个整数m、n和t，t表示骑士的初始血量。(m,n <= 20, t <= 30) 第2至m+1行描述了迷宫，迷宫以m行n列的方格组成，若方格为"."则表示骑士可以通过，若方格为"#"则表示墙，骑士不能通过，若方格为数字则表示怪物，数字为怪物的血量，保证怪物的血量小于10（一位数）。"*"表示了骑士当前所在的位置，"+"表示公主被囚禁的位置。
输出
若骑士能成功拯救公主，则输出骑士走到公主所囚禁方格所剩最大血量，否则输出0。
样例输入
5 6 10
..*...
.#2###
5#..4#
.##9.#
.#+..#
样例输出
4
参考答案
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
struct POINT
{
int x,y,tot; //坐标，步数
bool get_jewel[7],enchantment; //找到的宝石，结界
} point,door;
int main()
{
int k,F[4][2]={-1,0,1,0,0,-1,0,1};
scanf("%d",&k);
for(int kk=1;kk<=k;kk++)
{
/*定义*/
queue<POINT> que; //队列
int r,c,needkind,door_coord[15][2]={},sdoor_coord=0; //边界，需要的宝石种类,传送门坐标，传送门个数
char maze[205][205]={};//迷宫
bool walked[205][205][35]={},finish=false; //已经走过的路，第三维是宝石数(2进制)；是否完成
/*输入*/
scanf("%d%d%d",&r,&c,&needkind);
for(int i=0;i<r;i++)
{
scanf("%s",maze[i]);
for(int j=0;j<c;j++)
{
if(maze[i][j]=='S') //起点
{
memset(point.get_jewel,false,sizeof(point.get_jewel));
point.x=i;point.y=j;point.tot=0;point.enchantment=true;
}
if(maze[i][j]=='$') //传送门
{
door_coord[sdoor_coord][0]=i; //存入位置
door_coord[sdoor_coord++][1]=j;
}
}
}
/*广度优先搜索*/
que.push(point); //存入起点
while(!que.empty()) //队列不为空
{
for(int i=0;i<4;i++) //4个方向
{
point=que.front(); //直接等
point.tot++;point.x+=F[i][0];point.y+=F[i][1]; //改坐标，改步数
if(point.x<0 || point.x>=r || point.y<0 || point.y>=c || maze[point.x][point.y]=='#') continue;
//超界或为墙
if('0'<=maze[point.x][point.y] && maze[point.x][point.y]<='4') //如果为宝石
point.get_jewel[maze[point.x][point.y]-'0']=true; //改变point中该宝石的值为 “找到 ”
int sget_jewel=0,ss=0; //找到的宝石个数
for(int i=0;i<5;i++)
if(point.get_jewel[i]) //遍历宝石获得数
sget_jewel+=pow(2,i),ss++; //eg:获得0,3 --> 2进制：01001=9
if(walked[point.x][point.y][sget_jewel]) continue;
//如果之前到达过该位置且未找到更多的宝石
walked[point.x][point.y][sget_jewel]=true; //改变该位置的到达记录
if(ss>=needkind) point.enchantment=false; //如果找到了足够的宝石，结界消失
if(maze[point.x][point.y]=='$') //如果是传送门
{
door=point; //保存位置
for(int i=0;i<sdoor_coord;i++) //遍历所有传送门
if(door_coord[i][0]!=point.x || door_coord[i][1]!=point.y) //不是当前的位置
{
door.x=door_coord[i][0];door.y=door_coord[i][1]; //存入传送门
que.push(door);
}
}
if(maze[point.x][point.y]=='E' && !point.enchantment)
//如果是找到终点并且没有结界
{
printf("%d\n",point.tot);
finish=true; //找到
}
if(finish) break; //找到退出
que.push(point); //存入当前位置
}
if(finish) break; //找到退出
que.pop(); //出队
}
if(!finish) printf("oop!\n"); //没有找到
}
return 0;
}
上一题
下一题