题解 | #孙悟空救师傅#

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define endl '\n'

void init()
{
    
}

int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};
char a[105][105];
int dis[10][105][105];
int S[105][105];
void solve()
{
    int n,m;cin>>n>>m;
    int x0,y0;
    int cnt_s=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            cin>>a[i][j];
            if(a[i][j]=='K'){
                x0=i,y0=j;
            }
            else if(a[i][j]=='S')S[i][j]=cnt_s++;
        }
    if(n==1){
        cout<<"impossible"<<endl;
        return;
    }
    memset(dis,0x3f3f3f3f,sizeof(dis));
    struct node{
        int z,s,x,y;
    };
    queue<node>q;
    q.push({0,0,x0,y0});
    dis[0][x0][y0]=0;
    int ans=1e9;
    while(!q.empty()){
        auto [z,s,x,y]=q.front();
        q.pop();
        if(a[x][y]=='T'&&z==m){
            ans=dis[z][s][x][y];
            break;
            //ans=min(ans,dis[z][x][y]);
            //continue;
        }
        for(int i=0;i<4;i++){
            int xx=x+dx[i],yy=y+dy[i],zz=z,ss=s;
            if(xx<0||xx>=n||yy<0||yy>=n||a[xx][yy]=='#')continue;
            if(a[xx][yy]-'0'==zz+1)zz++;
            if(S[xx][yy]!=0&&!(s&1<<(S[xx][yy]-1))){
                ss=s|1<<(S[xx][yy]-1);
                if(dis[zz][xx][yy]>dis[z][x][y]+2){
                    dis[zz][xx][yy]=dis[z][x][y]+2;
                    q.push({zz,ss,xx,yy});
                }
            }
            else if(dis[zz][xx][yy]>dis[z][x][y]+1){
                dis[zz][xx][yy]=dis[z][x][y]+1;
                q.push({zz,ss,xx,yy});
            }
        }
    }
    if(ans==1e9)cout<<"impossible"<<endl;
    else cout<<ans<<endl;
    
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t=1;//cin>>t;
    init();
    while(t--)solve();
     
    return 0;
}