题目链接: 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[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 |