HDU 5025 (BFS+记忆化状压搜索)

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=5025

题目大意: 迷宫中孙悟空救唐僧,可以走回头路。必须收集完钥匙,且必须按顺序收集。迷宫中还有蛇,杀蛇多耗时1,蛇杀完就没了。问最少耗时。

解题思路

2014广州网赛的水题之一。当时没刷过BFS状压,结果悲剧了。

由于钥匙强制有序,所有得压蛇。

设f[x][y][key][snake]为在(x,y)点,已经取得的钥匙key,以及杀蛇snake的状态。

对于钥匙k,如果k==key+1,那么 key++

对于蛇k,如果!snake&(1<<k)那么dep++

其他情况则dep++即可

由于杀蛇导致BFS树同层分布不均衡,可以使用优先队列来优化。不过维护优先队列需要时间,可能效果适得其反orz。

#include "cstdio"
#include "string"
#include "cstring"
#include "iostream"
#include "queue"
using namespace std;
struct status
{
int x,y,dep,key,snake;
status(int x,int y,int dep,int key,int snake):x(x),y(y),dep(dep),key(key),snake(snake) {}
bool operator < (const status &a) const {return dep > a.dep;}
};
char map[][];
int n,m,sx,sy,ex,ey,f[][][][],dir[][]={-,,,,,-,,},ans;
void bfs(int x,int y)
{
priority_queue<status> Q;
Q.push(status(x,y,,,)) ;
f[x][y][][]=;
bool flag=false;
while(!Q.empty())
{
if(flag) break;
status t=Q.top();Q.pop();
for(int s=;s<;s++)
{
int X=t.x+dir[s][],Y=t.y+dir[s][],key=t.key,snake=t.snake,dep=t.dep;
if(X<||X>n||Y<||Y>n||map[X][Y]=='#') continue;
if(isdigit(map[X][Y]))
{
int k=map[X][Y]-'';
if(k==t.key+) key++;
}
if(islower(map[X][Y]))
{
int k=map[X][Y]-'a';
if(!(snake&(<<k))) {snake=snake|(<<k);dep++;}
}
dep++;
if(f[X][Y][key][snake]) continue;
f[X][Y][key][snake]=;
if(X==ex&&Y==ey&&key==m) {flag=true;ans=min(ans,dep);}
Q.push(status(X,Y,dep,key,snake));
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
string tt;
while(cin>>n>>m&&n)
{
int snake_cnt='a';
memset(f,,sizeof(f));
ans=<<;
for(int i=;i<=n;i++)
{
cin>>tt;
for(int j=;j<tt.size();j++)
{
map[i][j+]=tt[j];
if(tt[j]=='K') {sx=i;sy=j+;}
if(tt[j]=='T') {ex=i;ey=j+;}
if(tt[j]=='S') map[i][j+]=snake_cnt++;
}
}
bfs(sx,sy);
if(ans==<<) cout<<"impossible"<<endl;
else cout<<ans<<endl;
}
}
11878237 2014-10-15 16:46:24 Accepted 5025 812MS 15480K 2076 B C++ Physcal
上一篇:网络流(最大流) CodeForces 546E:Soldier and Traveling


下一篇:[HDU 1428]--漫步校园(记忆化搜索)