【HDU - 1429】胜利大逃亡(续) (高级搜索)【状…
2019-02-20 00:43:45来源:博客园 阅读 ()
Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……
这次魔王汲取了上次的教训,把Ignatius关在一个n*m的地牢里,并在地牢的某些地方安装了带锁的门,钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置,离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次,若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试,Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢,如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。
Input
每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图,其中包括:
. 代表路
* 代表墙
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙,对应的门分别为A-J
每组测试数据之间有一个空行。
Output
针对每组测试数据,如果可以成功逃亡,请输出需要多少分钟才能离开,如果不能则输出-1。
Sample Input
4 5 17 @A.B. a*.*. *..*^ c..b* 4 5 16 @A.B. a*.*. *..*^ c..b*
Sample Output
16 -1
题意:给n行m列的迷宫,还有t的时间,问能不能在t的时间内走出迷宫
思路:广搜+状态压缩
博主学到的:
1.状态压缩
这里有10把钥匙,有钥匙用1表示,没有钥匙用0表示,显然每把钥匙只有0和1两种状态,所以可以用2进制来存放钥匙的状态。
举个栗子:0101(这个是二进制表示,转化为十进制是5)表示当前有a钥匙和c钥匙
即第一把钥匙和第三把钥匙(abcd分别对应1234)
那怎么更新状态呢?这个时候我们要用到 与运算(&)和 或运算(|)
例如一开始你没有钥匙,此时状态为ys=0
当你走到b钥匙处,状态更新为ys=ys|(1<<'b'-'a');
此时ys=2,用二进制表示是0010,即拥有b钥匙
当你走到B门的时候,想知道自己有没有b钥匙,
则计算ys>>(‘B’-‘A’)&1的值(右移的优先级高于与,所以是先右移后与)
如果计算出值为1,则说明有这把钥匙。
2.状态标记(爆内存了几次,先记下来以后报仇.jpg)
为了避免来回走,我们设一个vis[x][y][ys]数组来表示当前状态是否经历过,如果经历过,就跳过(因为重复了)
注意同一个点,拥有的钥匙不同,这个点的状态也不同,有同样多的钥匙就没必要在这个点来回走
划重点:当检查到某个点能走时,把它放入队列并标记
一开始我把检查后能走的点放入队列中,等拿出这个点才对它进行标记,结果无限Memory Limit Exceeded
原因:假如有3个相邻的点,记为a b c,b是可以走的点,而且a和c在队列中
在队列中拿出a,b在a的右边,而且b可以走,所以b就放入了队列,a被标记
然后再队列中拿出c,b在c的左边,b没有被标记,b再次被放入队列,c被标记
问题来了,b被重复放入了队列,即使答案是正确的,但重复的点多次放入了队列
导致内存浪费,数据一旦很大,就会爆内存
所以标记要及时打上
下面是我的代码
#include <iostream> #include <queue> #include <cmath> #include <algorithm> #include <string.h> #include <stdio.h> using namespace std; int n,m,t; char a[22][22]; bool vis[22][22][1<<11];//10把钥匙状态用2进制存 int sx,sy,ex,ey; struct node{ int x,y,ys,step; }; queue<node> q; int dx[4]={-1,0,0,1}; int dy[4]={0,-1,1,0}; node now,nextt; bool check(node &b){ if(b.x>=1&&b.x<=n&&b.y>=1&&b.y<=m)//是否越界 { if(vis[b.x][b.y][b.ys]==0&&a[b.x][b.y]!='*')//是不是路,有没有走过 { if(a[b.x][b.y]>='A'&&a[b.x][b.y]<='J')//判断是不是门 { if((b.ys>>(a[b.x][b.y]-'A'))&1==1) { return true;//是门,有钥匙 } else return false;//是门没钥匙 } if(a[b.x][b.y]>='a'&&a[b.x][b.y]<='j')//判断是不是钥匙, { if((b.ys&(1<<a[b.x][b.y]-'a'))==0) { b.ys=b.ys|(1<<a[b.x][b.y]-'a'); return true; } else return true; } if(a[b.x][b.y]=='@'||a[b.x][b.y]=='^'||a[b.x][b.y]=='.') return true; //return true;//是起点,终点或者路 } else return false;//是障碍或者走过 } else return false;//越界 } int bfs(node now){ while(!q.empty()) { now=q.front(); q.pop(); if(now.step>=t) return -1; if(now.x==ex&&now.y==ey) return now.step; for(int i=0;i<4;i++){ nextt=now; nextt.x+=dx[i]; nextt.y+=dy[i]; nextt.step+=1; if(check(nextt)) {vis[nextt.x][nextt.y][nextt.ys]=1; q.push(nextt); } } } return -1 ; } int main() { while(cin>>n>>m>>t) { while(!q.empty()) { q.pop(); } memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>a[i][j]; if(a[i][j]=='@'){ sx=i; sy=j; } if(a[i][j]=='^'){ ex=i; ey=j; } } now.x=sx; now.y=sy; now.ys=0; now.step=0; q.push(now); int ans; ans=bfs(now); if(ans<t) cout<<ans<<endl; else cout<<-1<<endl; } return 0; }
原文链接:https://www.cnblogs.com/Remilia-Scarlet/p/10386564.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:匿名管道通讯实现
下一篇:算法训练 区间k大数查询
- HDU-2955-Robberies(0-1背包) 2020-03-30
- hdu1455 拼木棍(经典dfs) 2020-02-29
- anniversary party_hdu1520 2020-02-16
- hdu1062 text reverse 2020-01-27
- hdu4841 2020-01-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash