胜利大逃亡(续) hdu-1429 (bfs状态压缩)
程序员文章站
2024-03-23 22:58:22
...
题目链接:胜利大逃亡(续)
题解:
整体思路:
找到钥匙后就存起来,找到门时判断当前所需钥匙是否已经找到,若找到,当前门可走,否则,不可走。直到找到出口为止。
具体思路:
用二进制来存钥匙,比如说:111,代表1、2、3钥匙都找到了,而100表示只有3钥匙。那应该如何储存呢。当找到x钥匙时,用sta表示当前状态,则sta=1<< (x-1),也就是将1在二进制中左移(x-1)位。state表示当前储存钥匙的状态,state=state|sta,将钥匙存到状态中 ;
当找到门时,用sta表示当前门所需要钥匙的状态,然后判断(sta&state)是否为0,若为0则说明当前门没有钥匙,否则则有。
此题的的标记数组也需要钥匙的状态来判定是否标记。当再次经过x,y时,若此时的钥匙状态和上次经过时的钥匙状态相比没有改变,则此时不能重复走此点。
代码:
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
char Map[22][22];///地图;
int c[4][2]= {1,0,0,1,0,-1,-1,0};///方向数组;
int vis[22][22][10100]= {0};///标记数组;
int n,m,t;
struct yun
{
int x,y,s;
int state;
};
int bfs(int x,int y)
{
queue<yun> Q;
yun st,en;
st.x=x;
st.y=y;
st.state=0;
st.s=0;
vis[x][y][0]=1;
Q.push(st);
while(Q.size())
{
st=Q.front();
Q.pop();
for(int i=0; i<4; i++)
{
int dx=st.x+c[i][0];
int dy=st.y+c[i][1];
if(dx<0||dy<0||dx>=n||dy>=m||Map[dx][dy]=='*')
continue;
en.state=st.state;
if(Map[dx][dy]>='a'&&Map[dx][dy]<='j')///找到钥匙;
{
int sta=1;
sta=sta<<(Map[dx][dy]-'a');
en.state=st.state|sta;///存入状态;
}
if(Map[dx][dy]>='A'&&Map[dx][dy]<='J')///找到门;
{
int sta=1;
sta=sta<<(Map[dx][dy]-'A');
if((st.state&sta)==0)///(括号别忘带)判断是否有钥匙;
continue;
}
if(Map[dx][dy]=='^'&&st.s+1<t)///找到出口;
return st.s+1;
if(vis[dx][dy][en.state])///再次访问此状态;
continue;
vis[dx][dy][en.state]=1;
en.x=dx;
en.y=dy;
en.s=st.s+1;
Q.push(en);
}
}
return -1;
}
int main()
{
int i,j,s_x,s_y;
while(~scanf("%d%d%d",&n,&m,&t))
{
memset(vis,0,sizeof(vis));
for(i=0; i<n; i++)
{
scanf("%s",Map[i]);
for(j=0; j<m; j++)
{
if(Map[i][j]=='@')
{
s_x=i;
s_y=j;
}
}
}
int ans=bfs(s_x,s_y);
printf("%d\n",ans);
}
}
上一篇: Netty 之 心跳检测