HDU 5025(BFS+記憶化状圧探索)
10900 ワード
タイトルリンク: http://acm.hdu.edu.cn/showproblem.php?pid=5025
迷宮の中で孫悟空は唐僧を救って、振り返る道を歩むことができます.鍵は収集済みで、順番に収集しなければなりません.迷宮には蛇もいます.蛇を殺すのに時間がかかります.蛇を殺すのに時間がかかります.聞くのに少なくとも時間がかかる.
問題解決の考え方:
2014広州ネット試合の水題の一つ.当時BFS状の圧力をかけたことがなく、悲劇になった.
鍵が強制的に秩序化されているため、蛇を押さなければならない.
f[x][y][key][snake]を(x,y)点において、既に取得している鍵keyと、ヘビsnakeを殺した状態とする.
キーkの場合、k=key+1の場合、key++
ヘビkに対して、もし!snake&(1<その他の場合はdep++でよい
ヘビを殺すことによってBFSツリーの同層分布が不均衡になるため,優先キューを用いて最適化することができる.ただし、優先キューのメンテナンスには時間がかかり、逆orzになる可能性があります.
11878237
2014-10-15 16:46:24
Accepted
5025
812MS
15480K
2076 B
C++
Physcal
迷宮の中で孫悟空は唐僧を救って、振り返る道を歩むことができます.鍵は収集済みで、順番に収集しなければなりません.迷宮には蛇もいます.蛇を殺すのに時間がかかります.蛇を殺すのに時間がかかります.聞くのに少なくとも時間がかかる.
問題解決の考え方:
2014広州ネット試合の水題の一つ.当時BFS状の圧力をかけたことがなく、悲劇になった.
鍵が強制的に秩序化されているため、蛇を押さなければならない.
f[x][y][key][snake]を(x,y)点において、既に取得している鍵keyと、ヘビsnakeを殺した状態とする.
キーkの場合、k=key+1の場合、key++
ヘビkに対して、もし!snake&(1<
ヘビを殺すことによって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[105][105];
int n,m,sx,sy,ex,ey,f[105][105][10][35],dir[4][2]={-1,0,1,0,0,-1,0,1},ans;
void bfs(int x,int y)
{
priority_queue<status> Q;
Q.push(status(x,y,0,0,0)) ;
f[x][y][0][0]=1;
bool flag=false;
while(!Q.empty())
{
if(flag) break;
status t=Q.top();Q.pop();
for(int s=0;s<4;s++)
{
int X=t.x+dir[s][0],Y=t.y+dir[s][1],key=t.key,snake=t.snake,dep=t.dep;
if(X<1||X>n||Y<1||Y>n||map[X][Y]=='#') continue;
if(isdigit(map[X][Y]))
{
int k=map[X][Y]-'0';
if(k==t.key+1) key++;
}
if(islower(map[X][Y]))
{
int k=map[X][Y]-'a';
if(!(snake&(1<<k))) {snake=snake|(1<<k);dep++;}
}
dep++;
if(f[X][Y][key][snake]) continue;
f[X][Y][key][snake]=1;
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,0,sizeof(f));
ans=1<<28;
for(int i=1;i<=n;i++)
{
cin>>tt;
for(int j=0;j<tt.size();j++)
{
map[i][j+1]=tt[j];
if(tt[j]=='K') {sx=i;sy=j+1;}
if(tt[j]=='T') {ex=i;ey=j+1;}
if(tt[j]=='S') map[i][j+1]=snake_cnt++;
}
}
bfs(sx,sy);
if(ans==1<<28) cout<<"impossible"<<endl;
else cout<<ans<<endl;
}
}
11878237
2014-10-15 16:46:24
Accepted
5025
812MS
15480K
2076 B
C++
Physcal