孙悟空救师傅

链接：https://ac.nowcoder.com/acm/problem/235903 来源：牛客网

师傅又被妖怪抓走了。师傅被困的宫殿可以看作一个 n×nn\times nn×n 的由字符构成的矩阵，每一个字符表示一个房间。字符'K'表示孙悟空的起始位置，'T'表示师傅被困的位置，'S'表示有蛇的房间，'.'表示空房间，'#'表示无法进入的房间。矩阵中包含且仅包含一个'K'和一个'T'。

每分钟，孙悟空都可以上下左右移动一格，如果遇到蛇，打倒蛇需要额外花费一分钟，保证地图上最多有五个有蛇的房间。此外孙悟空还需要集齐所有种类的钥匙才能救出师傅。钥匙的种类以 1,2,...,m1,2,...,m1,2,...,m 的顺序编号，且钥匙需要按照顺序拿。具体来说，孙悟空能拿第 iii 种钥匙，当且仅当对于 ∀j,1≤j<i\forall j, 1\le j\lt i∀j,1≤j<i 且 jjj 种类的钥匙都已经拿到至少一把。除了'#'的房间，其它所有房间都可以经过。孙悟空想要尽快救出师傅，你能帮帮他吗。

做法

首先数一下这里要处理的东西，必须按顺序拿到m把钥匙，第一次遇到S时需要多停留一秒（不确定是不是第一次），然后就是不能直接标记走过的路。钥匙的拿取比较好想到，我们用一个变量表示当前拿的是几号钥匙，当下一个标号的钥匙出现时才能去拿。那么就是考虑怎么在不mle的情况下标记出走过S房间的情况和怎么·尽量少往队列里面放东西。这里我们就不把状态数放进队列里面考虑，我们能更新答案的情况就是到达师傅那里时，已经拿到了m把钥匙，那么，就算我有无数种情况都能到，我也优先选择步数最短的情况，所以不需要去计算一些useless的状态，我们另开一个三维数组，表示在拿到k把钥匙的情况下走到坐标x，y的最短步数，而我们需要更新数组的情况只有当我们走到S时，下一步情况的数组步数大于上一步的步数+2，我们把他更新为上一步的步数+2，或者没有走到S，但下一步在数组的步数大于上一步（这一步，相对下一步的上一步，上同），更新数组，其他情况就不需要操作，只有当我们修改数组时才把相应状态放进队列即可。所以一开始的三维数组要初始化一个较大的值。（ps：上面的写法大体没错，但之后成功被qcjj hack，原因是第二次经过S的情况没有处理导致每一次走到S都会多停留1秒，所以当我们走到S后，将S修改为‘.’即可，更正一下之前题解的错误） 注意我们是bfs，所以第一次满足条件的一定是最小值，如果不及时停止可能会导致错误（没理解）

//本题代码
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
/*inline __int128 read(){
    __int128 x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}*/
//dont forget to check long long
//别写重变量名
//记得判越界
//别死磕
//处理字符串删掉关流
//用__int128时记得删掉关流
int vis[110][110][100];
struct node
{
    int pos,key;  
};
int n,m,sx=0,sy=0,edx=0,edy=0,ans=0;
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
char s[110][110];
std::queue<node> q;
int bfs()
{
    q.push((node){sx*n+sy,0});
    vis[sx][sy][0]=0;
    while(!q.empty())
    {
        auto t=q.front();
        q.pop();
        int x=t.pos/n,y=t.pos%n;
        int cnt=t.key;
        if(s[x][y]=='T'&&cnt==m)
        {
            //std::cout<<vis[x][y][cnt]<<endl;
            return vis[x][y][cnt];
        }
       // std::cout<<x<<" "<<y<<" "<<cnt<<endl;
        for(int i=0;i<4;i++)
        {
            int dx=x+d[i][0];
            int dy=y+d[i][1];
            int dcnt=cnt;
            if(dx<0||dy<0||dx>=n||dy>=n||s[dx][dy]=='#') continue;
             if(s[dx][dy]>='0'&&s[dx][dy]<='9'&&(s[dx][dy]-'0'-1)==dcnt) dcnt+=1;
            if(s[dx][dy]=='S') 
            {
                if(vis[dx][dy][dcnt]>vis[x][y][cnt]+2) {
                     s[dx][dy]='.';
                    vis[dx][dy][dcnt]=vis[x][y][cnt]+2;
                 q.push((node){dx*n+dy,dcnt});
                }
            }
            else
            {
                if(vis[dx][dy][dcnt]>vis[x][y][cnt]+1) {vis[dx][dy][dcnt]=vis[x][y][cnt]+1;
                 q.push((node){dx*n+dy,dcnt});}
            }
        }
    }
    return -1;
}
void slove()
{
   std::cin>>n>>m;
   for(int i=0;i<n;i++)
   {
        for(int j=0;j<n;j++)
        {
            std::cin>>s[i][j];
            if(s[i][j]=='K') 
            {
                sx=i;
                sy=j;
            }
            else if(s[i][j]=='T')
            {
                edx=i;
                edy=j;
            }
        }
   }
   memset(vis,0x3f,sizeof(vis));
    ans=bfs();
    if(ans==-1) std::cout<<"impossible"<<endl;
    else std::cout<<ans<<endl;
    //std::cout<<sx<<" "<<sy<<" "<<edx<<" "<<edy<<endl;
   


}
int main()
{
    int T=1; 
    //std::cin>>T;
    while(T--)    {
        slove();
    }

    return 0;
}