百练题目地址
判重3个状态就够了 位置+钥匙
除了#位置，其他位置都可以经过多次
注意钥匙数可以为零
因为打蛇要time+2，所以用优先队列
蛇的数量<=5,所以1<<5的数就足够保存蛇的状态了
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100+5;
int N,K,vis[maxn][maxn][10]; //判重三个状态表示就够了
int r0,c0,r1,c1;
char G[maxn][maxn];
struct Point{int x,y,time,key,snack;Point(int x,int y,int t,int k,int s):x(x),y(y),time(t),key(k),snack(s){} bool operator < (const Point& p) const {return time>p.time;}
};
bool inside(int x,int y)
{return x>=0&&x<N&&y>=0&&y<N;
}
int bfs(int r,int c)
{priority_queue<Point> Q;Q.push(Point(r,c,0,0,0));vis[r][c][0]=1;while(!Q.empty()){int x=Q.top().x, y=Q.top().y, time=Q.top().time, key=Q.top().key, snack=Q.top().snack; Q.pop();if(key==K&&x==r1&&y==c1) return time;for(int dx=-1;dx<=1;dx++)for(int dy=-1;dy<=1;dy++){if((dx&&dy)||(!dx&&!dy)) continue;int nx=x+dx;int ny=y+dy;if(!inside(nx,ny)||G[nx][ny]=='#') continue;if(isalpha(G[nx][ny])){ //遇到蛇判断是否曾经走过 bool killed=(1<<(G[nx][ny]-'A'))&snack;int ns=snack+(1<<(G[nx][ny]-'A'));if(killed&&!vis[nx][ny][key]) {Q.push(Point(nx,ny,time+1,key,snack));vis[nx][ny][key]=1;}else if(!killed&&!vis[nx][ny][key]) {vis[nx][ny][key]=1;Q.push(Point(nx,ny,time+2,key,ns));}}else {if(!vis[nx][ny][key]) { //除了蛇之外都可以走 vis[nx][ny][key]=1;Q.push(Point(nx,ny,time+1,key,snack));}if(isdigit(G[nx][ny])){ //拿钥匙 int nkey=G[nx][ny]-'0';if(nkey==key+1&&!vis[nx][ny][nkey]){Q.push(Point(nx,ny,time+1,nkey,snack));vis[nx][ny][nkey]=1;}} }}}return -1;
}
int main()
{while(scanf("%d%d",&N,&K)==2&&N) //K可以等于0 {int cnt=0;for(int i=0;i<N;i++)for(int j=0;j<N;j++){cin>>G[i][j];if(G[i][j]=='K') r0=i,c0=j,G[i][j]='.';else if(G[i][j]=='T') r1=i,c1=j,G[i][j]='.';else if(G[i][j]=='S') G[i][j]='A'+cnt++; //给蛇编号 }memset(vis,0,sizeof(vis));int ans=bfs(r0,c0);if(ans==-1) cout<<"impossible"<<endl;else cout<<ans<<endl;}return 0;
}