点击打开链接

题意：从K走到T，S为怪，走的时候就多花费一秒，走到T时收集m把不同的钥匙。可是规定收集n之前，必须1~n-1所有收集完成，怪最多有5个

思路：怪最多就有5个，然后钥匙是1~9把，我们每一个点的状态就不会非常多，在BFS时每一个点的状态进行标记即可了。5个怪状态压缩着推断，由于这个怪在第二次经过的时候已经死了，不用花费时间去杀死它

#include <map>

#include <queue>

#include <stdio.h>

#include <iostream>

#include <string.h>

#include <stdlib.h>

#include <algorithm>

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const int maxn=110;

int sx,sy,ex,ey,n,m,cnt;

int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

int vis[maxn][maxn][10][40];

char str[maxn][maxn];

struct edge{

    int x,y,step,numkey,ss;

};

struct snake{

    int x,y;

}sna[10];

int bfs(){

    queue<edge>que;

    edge c,ne;

    memset(vis,0,sizeof(vis));

    c.x=sx,c.y=sy,c.step=0,c.numkey=0,c.ss=0;

    vis[c.x][c.y][0][0]=1;

    que.push(c);

    int ans=inf;

    while(!que.empty()){

        c=que.front();que.pop();

        if(c.x==ex&&c.y==ey&&c.numkey==m){

            ans=min(ans,c.step);

        }

        for(int i=0;i<4;i++){

            int xx=dir[i][0]+c.x;

            int yy=dir[i][1]+c.y;

            if(xx<0||xx>n-1||yy<0||yy>n-1||str[xx][yy]=='#') continue;

            if(vis[xx][yy][c.numkey][c.ss]) continue;

            ne.x=xx;ne.y=yy;ne.step=c.step+1;ne.numkey=c.numkey;ne.ss=c.ss;

            if(str[xx][yy]>='1'&&str[xx][yy]<='9'){//假设走到的是钥匙的位置进行推断

                int t=str[xx][yy]-'0';

                if(ne.numkey==t-1){//钥匙刚好是当前钥匙数+1，就符合条件

                    ne.numkey++;

                    vis[ne.x][ne.y][ne.numkey][ne.ss]=1;

                    que.push(ne);

                }else{//不符合直接压进队列

                    vis[ne.x][ne.y][ne.numkey][ne.ss]=1;

                    que.push(ne);

                }

            }else if(str[xx][yy]=='S'){//遇到怪进行推断

                for(int i=0;i<cnt;i++){

                    if(xx==sna[i].x&&yy==sna[i].y){

                        if((ne.ss>>i)&1){//说明这个怪已经死掉了

                            vis[ne.x][ne.y][ne.numkey][ne.ss]=1;

                            que.push(ne);

                        }else{//没有死掉的话时间+1，状态更新

                            ne.step++;

                            ne.ss+=(1<<i);

                            vis[ne.x][ne.y][ne.numkey][ne.ss]=1;

                            que.push(ne);

                        }

                        break;

                    }

                }

            }else{

                vis[ne.x][ne.y][ne.numkey][ne.ss]=1;

                que.push(ne);

            }

        }

    }

    return ans;

}

int main(){

    while(scanf("%d%d",&n,&m)!=-1){

        if(n==0&&m==0) break;

        cnt=0;

        for(int i=0;i<n;i++) scanf("%s",str[i]);

        for(int i=0;i<n;i++){

            for(int j=0;j<n;j++){

                if(str[i][j]=='K')sx=i,sy=j;

                if(str[i][j]=='T')ex=i,ey=j;

                if(str[i][j]=='S'){

                    sna[cnt].x=i,

                    sna[cnt++].y=j;//记录怪的位置和数量

                }

            }

        }

        int ans=bfs();

        if(ans==inf) puts("impossible");

        else printf("%d\n",ans);

    }

    return 0;

}