hdu5025 Saving Tang Monk
传送门
题意
有一个(n*n(1leq nleq 100))的矩阵，要求从起点(K)走到终点(T)并且拿到(m(0leq mleq 9))个钥匙，每次只能向相邻的四个点的方向移动一步，耗费一分钟时间，钥匙只能按照编号从小到大的顺序依次拿到，矩阵中还有数量不超过5条的蛇，走到有蛇的点需要杀蛇，杀蛇耗费一分钟时间，计算所需的最短时间
题解
状态压缩+bfs
由于钥匙只能按照从小到大的顺序来拿，所以钥匙的状态只需要记录数量
蛇的状态通过状态压缩记录
同时需要记录当前点的x坐标和y坐标
所以通过四维矩阵记录所有状态，进行bfs，由于杀蛇需要多花费时间，导致bfs树的同层节点不一定在队列中连续，所以可以使用优先队列，但是优先队列需要维护，最终不一定能达到优化效果（结果显示本题使用队列更快一些）
队列
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=102,maxm=12,inf=0x3f3f3f3f;
int n,m,book[maxm][1<<6][maxn][maxn],sx,sy,dx,dy,dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char a[maxn][maxn];
struct node{
int key,s,x,y,step;
node(int key,int s,int x,int y,int step):key(key),s(s),x(x),y(y),step(step){}
};
queue<node> q;
void init(){
memset(book,0,sizeof(book));
char c='a';
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]=='K'){
sx=i;
sy=j;
}
if(a[i][j]=='T'){
dx=i;
dy=j;
}
if(a[i][j]=='S'){
a[i][j]=c;
c++;
}
}
}
while(!q.empty()) q.pop();
}
int bfs(){
int ans=inf;
node cur(0,0,sx,sy,0);
q.push(cur);
while(!q.empty()){
node cur=q.front();
q.pop();
int key=cur.key,s=cur.s,x=cur.x,y=cur.y,step=cur.step;
if(x==dx && y==dy && key==m){
ans=min(ans,step);
}
if(book[key][s][x][y]) continue;
book[key][s][x][y]=1;
for(int k=0;k<4;k++){
int tx=x+dir[k][0],ty=y+dir[k][1];
if(tx>=0 && tx<n && ty>=0 && ty<n && a[tx][ty]!='#'){
int key_=key,s_=s,step_=step+1;
if(a[tx][ty]>='a' && a[tx][ty]<='e'){
if((s_&(1<<a[tx][ty]-'a'))==0){
int id=a[tx][ty]-'a';
s_=s_|(1<<id);
step_++;
}
}
else if(a[tx][ty]>='1' && a[tx][ty]<='9'){
int id=a[tx][ty]-'0';
if(key_+1==id) key_++;
}
if(!book[key_][s_][tx][ty]){
node nxt(key_,s_,tx,ty,step_);
q.push(nxt);
}
}
}
}
if(ans==inf) ans=-1;
return ans;
}
int main(){
while(~scanf("%d %d",&n,&m) && (n || m)){
for(int i=0;i<n;i++) scanf("%s",a[i]);
init();
int ans=bfs();
if(ans!=-1) printf("%d
",ans);
else printf("impossible
");
}
return 0;
}
优先队列
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=102,maxm=12;
int n,m,book[maxm][1<<5][maxn][maxn],sx,sy,dx,dy,dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char a[maxn][maxn];
struct node{
int key,s,x,y,step;
node(int key,int s,int x,int y,int step):key(key),s(s),x(x),y(y),step(step){}
friend bool operator < (node t1,node t2){
return t1.step>t2.step;
}
};
priority_queue<node> pq;
void init(){
memset(book,0,sizeof(book));
char c='a';
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]=='K'){
sx=i;
sy=j;
}
if(a[i][j]=='T'){
dx=i;
dy=j;
}
if(a[i][j]=='S'){
a[i][j]=c;
c++;
}
}
}
while(!pq.empty()) pq.pop();
}
int bfs(){
node cur(0,0,sx,sy,0);
pq.push(cur);
while(!pq.empty()){
node cur=pq.top();
pq.pop();
int key=cur.key,s=cur.s,x=cur.x,y=cur.y,step=cur.step;
if(x==dx && y==dy && key==m) return step;
if(book[key][s][x][y]) continue;
book[key][s][x][y]=1;
for(int k=0;k<4;k++){
int tx=x+dir[k][0],ty=y+dir[k][1];
if(tx>=0 && tx<n && ty>=0 && ty<n && a[tx][ty]!='#'){
int key_=key,s_=s,step_=step+1;
if(a[tx][ty]>='a' && a[tx][ty]<='e'){
if((s_&(1<<a[tx][ty]-'a'))==0){
s_|=(1<<a[tx][ty]-'a');
step_++;
}
}
else if(a[tx][ty]>='1' && a[tx][ty]<='9'){
int id=a[tx][ty]-'0';
if(key_==id-1) key_++;
}
if(!book[key_][s_][tx][ty]){
node nxt(key_,s_,tx,ty,step_);
pq.push(nxt);
}
}
}
}
return -1;
}
int main(){
while(~scanf("%d %d",&n,&m) && (n || m)){
for(int i=0;i<n;i++) scanf("%s",a[i]);
init();
int ans=bfs();
if(ans!=-1) printf("%d
",ans);
else printf("impossible
");
}
return 0;
}