【HDU - 1429】胜利大逃亡(续) (高级搜索)【状态压缩+BFS】
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; }
上一篇: 非洲艾滋病最多的国家排名 非洲艾滋病最多的国家是?
下一篇: 视频号的“提到”功能,如何高效引流