openjudge_2.5基本算法之搜索_7221:拯救公主

题目

7221:拯救公主
总时间限制: 1000ms 内存限制: 65536kB
描述
多灾多难的公主又被大魔王抓走啦!国王派遣了第一勇士阿福去拯救她。

身为超级厉害的术士,同时也是阿福的好伙伴,你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图,上面标记了阿福和公主所在的位置,以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门,通过一个传送门可以瞬间转移到任意一个传送门,当然阿福也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外,你还查探到公主所在的地方被设下了结界,需要集齐K种宝石才能打开。当然,你在地图上也标记出了不同宝石所在的位置。

你希望阿福能够带着公主早日凯旋。于是在阿福出发之前,你还需要为阿福计算出他最快救出公主的时间。

地图用一个R×C的字符矩阵来表示。字符S表示阿福所在的位置,字符E表示公主所在的位置,字符#表示不能踏入的禁区,字符$表示传送门,字符.表示该位置安全,数字字符0至4表示了宝石的类型。阿福每次可以从当前的位置走到他上下左右四个方向上的任意一个位置,但不能走出地图边界。阿福每走一步需要花费1个单位时间,从一个传送门到达另一个传送门不需要花费时间。当阿福走到宝石所在的位置时,就视为得到了该宝石,不需要花费额外时间。

输入
第一行是一个正整数T(1 <= T <= 10),表示一共有T组数据。
每一组数据的第一行包含了三个用空格分开的正整数R、C(2 <= R, C <= 200)和K,表示地图是一个R×C的矩阵,而阿福需要集齐K种宝石才能够打开拘禁公主的结界。
接下来的R行描述了地图的具体内容,每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。$的数量不超过10个。宝石的类型在数字0至4范围内,即不会超过5种宝石。
输出
对于每一组数据,输出阿福救出公主所花费的最少单位时间。若阿福无法救出公主,则输出“oop!”(只输出引号里面的内容,不输出引号)。每组数据的输出结果占一行。
样例输入
1
7 8 2

…S…#0.
.##…1…
.0#…
…1#…
…##E…
…1…
样例输出
11

理解

1.宽搜可以找到最短距离
2.凑齐宝石可以打开结界
不能只标记坐标,还要标记拥有宝石种类状况
没有宝石时到达的标记
有一种宝石时标记
两种三种都要标记
3.用二进制对应数字表示不同状态
如共四个宝贝
无宝石 0000 0
第0种 0001 1
第1种 0010 2
0、1 0011 3
第3种 0100 4
0、3 0101 5
以此类推。
不仅标记那种状态
还要记住该种状态到达所用时间
当然可以合到一起,所用时间0标记没来过,非零就是来过
4.四个宝贝,最大值是pow(2,0)+pow(2,1)+pow(2,2)+pow(2,3)=15。
就是状态是15就表示宝石凑齐。
5.传送门,不耗时,只要不是门自己就可以去。当然要判断该状态下去过没。
6.题目有问题,根据不同地图的测评,发现ac代码要求S点只能出发一次,再不能借过。
其实从题意里看不到这个概念,持有不同宝石时(不同状态时),是可以结果的。
本代码就没有强调这点,也还AC了。这里不解!!!
7.题目几个宝石就是几个,不能因为地图中出现的宝石收干扰
8.到达某个点后,不仅当前状态要增加,别的状态也得传递。所以最好还是拷贝节点。
但是不能拷贝各状态是否走过的标记,会超时
9.从某点出发,能不能到周边点,不是看目的地状态,而是出发点的状态
10.x!=dx||y!=dy行列有一个不同就非同点。

代码

#include <bits/stdc++.h>
using namespace std;
struct point{
char c;//地图字符
int x,y,//节点坐标
t,//步数
td;//状态,用数字表示拥有哪些宝石
bool k[5],//有哪些宝石
kt[31];//拥有哪些宝石时是否走过,(没用上,用不成,会超时)
point(){
memset(k,0,sizeof(k));
memset(kt,0,sizeof(kt));
t=0;td=0;
}
point(char cx,int xx,int yx){
memset(k,0,sizeof(k));
memset(kt,0,sizeof(kt));
c=cx,x=xx,y=yx;t=0;td=0;
}
}p[201][201],p1,p2,p3,door[15];
int t,ans,h,w,
km,//宝石种类数量
dm,//传送门数量
x,y,
md,//最大状态数
d[4][2]={0,-1,-1,0,0,1,1,0};
char c;
bool k[201][201][31];//标记每个点持有不同宝石时是否走过。
void view(point px){
cout<<px.x<<“\t”<<px.y<<endl;
cout<<“列:\t”;
for(int j=1;j<=w;j++)cout<<setw(8)<<j<<“\t”;cout<<endl;
for(int i=1;i<=h;i++){
cout<<i<<“行:\t”;
for(int j=1;j<=w;j++){
cout<<p[i][j].c<<“,”<<p[i][j].t<<“:”;
for(int x=0;x<=md;x++)cout<<setw(2)<<p[i][j].kt[x];
cout<<“\t”;
}cout<<endl;
}
}
bool ok(point p){//判定宝石带全否
for(int i=0;i<km;i++)if(!p.k[i])return 0;
return 1;
}
int main(){
freopen(“data.cpp”,“r”,stdin);
cin>>t;
while(t–){//多组数据
cin>>h>>w>>km;
md=0;
for(int i=0;i<km;i++)md+=pow(2,i);
memset(k,0,sizeof(k));//初始化
queue q;
ans=h * w;dm=0;
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++){
cin>>c;
p[i][j]=point{c,i,j};//初始化地图每个节点
if(c==‘S’){
q.push(p[i][j]);
p[i][j].kt[0]=1;//没宝石时标记走过(本题中没有用到)
}else if(c==’ $ ‘)door[dm++]=p[i][j];
}
while(!q.empty()){
p1=q.front();q.pop();
if(p1.c==‘E’&&ok(p1)){
ans=p1.t;break;
}
view(p1);
for(int i=0;i<4;i++){
x=p1.x+d[i][0],y=p1.y+d[i][1];c=p[x][y].c;
if(x<1||x>h||y<1||y>w||c==’#‘)continue;
p2=p1;
p2.x=x,p2.y=y,p2.t=p1.t+1;p2.c=c;
if(c>=‘0’&&c<km+‘0’){//多了个宝石
if(!p2.k[c-‘0’]){
p2.k[c-‘0’]=1;
p2.td+=pow(2,c-‘0’);//调整状态
}
}
//if(p[x][y].kt[td])continue;
//p2.kt[td]=1;//该两句没有用到,用了会反馈超时
if(k[x][y][p2.td])continue;//如果已经走过,不再走
k[x][y][p2.td]=1;//标记此节点此状态已走过。
p[x][y]=p2;
if(c==’$')
for(int j=0;j<dm;j++){
int dx=door[j].x,dy=door[j].y;
if(!(dx= =x&&dy= =y)){//只要不是门本身就传送
p3=p2;
p3.x=dx,p3.y=dy,p3.c=door[j].c;
p[dx][dy]=door[j]=p3;
q.push(door[j]);//传送门出发
}
}
q.push(p2);//本节点出发
}
}
if(ans==w * h)cout<<“oop!”<<endl;
else cout<<ans<<endl;
}
return 0;
}

小结

还是宽搜,找最短距离
因为宝石可以继承,所以到达点先继承出发点,再修改成本节点。
用持有宝石的品种数——多状态标记是否走过某个节点。
而这个多状态k[201][201][31]必须是独立的数组,放在节点里会超时(这个不理解,哪位仁兄给个指点)!


http://www.niftyadmin.cn/n/5514255.html

相关文章

mac读不出来ntfs mac硬盘读不出来盘

新买的Mac电脑由于需要导入旧电脑的数据&#xff0c;因此通常会读取备份硬盘&#xff0c;通过硬盘进行导入。不过由于各种原因&#xff0c;有些mac用户反馈无法正常读取或写入NTFS移动硬盘&#xff0c;下面就通过本篇教程&#xff0c;简单讲述当mac读不出来ntfs&#xff0c;mac…

RabbitMQ-Stream(高级详解)

文章目录 什么是流何时使用 RabbitMQ Stream&#xff1f;在 RabbitMQ 中使用流的其他方式基本使用Offset参数chunk Stream 插件服务端消息偏移量追踪示例 示例应用程序RabbitMQ 流 Java API概述环境创建具有所有默认值的环境使用 URI 创建环境创建具有多个 URI 的环境 启用 TLS…

C#——集合List

list list集合和Arraylist基本一样&#xff0c;只不过list是C#2.0版本新加入的范型类型。list也可以通过索引操作里面的元素&#xff0c;也有对list进行增删改查 概念 Array静态数组 * Arraylist 动态数组 * list集合 * 1. Array是容量是固定的&#xff0c;但是ArrayList和…

FileZilla:不安全的服务器,不支持 FTP over TLS 原因与解决方法

今天在用FileZilla Client连接某个主机的FTP的时候&#xff0c;主机地址、账号、密码、端口确定百分之百正确的情况下&#xff0c;结果报错如下&#xff1a; 状态: 正在解析 x.x.x 的地址 状态: 正在连接 x.x.x.x:21... 状态: 连接建立&#xff0c;等待欢迎消息... 状态: 不安全…

数组中的map方法

JavaScript中的map()方法详解 map()方法经常拿来遍历数组&#xff0c;但是不改变原数组&#xff0c;但是会返回一个新的数组&#xff0c;并且这个新的数组不会改变原数组的长度 注意&#xff1a;有时候会出现这种现象&#xff0c;出现几个undefined const array [1, 4,9, 16…

【端午惊喜】2024年6月6日 docker 国内镜像源集体失效

文章目录 概述中科大镜像源阿里镜像源其他镜像源可用的镜像源写在最后 概述 大家都知道使用docker hub官方镜像需要魔法&#xff0c;虽然大部人有魔法&#xff0c;但是网速也是很慢&#xff0c;还有部分同学没有&#xff0c;全靠国内各大厂商的镜像源&#xff0c;可是端午6.6大…

fastapi搭建的python项目,怎么才能出来API接口文档

使用 FastAPI&#xff0c;你可以轻松生成和测试 API 接口文档。FastAPI 内置了自动生成文档的功能&#xff0c;并且提供了交互式的 API 文档界面。 以下是如何生成和测试 API 接口文档的步骤&#xff1a; 确保项目结构正确&#xff1a; main.py 应该包含 FastAPI 应用实例和路…

防止设计图纸泄露:挑选合适的图纸加密解决方案

在技术迅猛发展的今天&#xff0c;企业的技术资产和知识产权成为了竞争的核心。图纸作为创新成果的直接体现&#xff0c;其安全性保护显得尤为重要。本文将探讨如何通过加密软件有效保护企业图纸&#xff0c;防止信息泄露。 一、图纸加密的必要性 图纸加密是确保企业技术资产安…