题解 | #小红勇闯地下城#

#include <queue>
#include<vector>
#include<string>
#include<algorithm>


#define int long long
#define endl "\n"
#define vt vector
#define pb push_back
using namespace std;
const int IMF=1e18+5;

const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};

struct T{
    int ln,lm,d;
    T(int x,int y,int z){
        ln=x,lm=y,d=z;
    }
    bool operator>(const T&other) const{
        return d>other.d;
    }
};

signed main(){
    int q;
    cin>>q;
    while(q--){
        int n,m,h;cin>>n>>m>>h;
        vt<vt<int>> op(n,vt<int>(m,0));
        vt<string> ed(n);
        int sn=-1,sm=-1;
        int fn=-1,fm=-1;
        for(int i=0;i<n;i++){
            cin>>ed[i];
          for(int j=0;j<m;j++){
            if(ed[i][j]=='S') sn=i,sm=j,op[i][j]=0;
            else if(ed[i][j]=='T') fn=i,fm=j,op[i][j]=0;
            else op[i][j]=ed[i][j]-'0';
          }
        }
       priority_queue<T,vt<T>,greater<T>> res;
       res.push({sn,sm,0});
       vt<vt<bool>> vst(n,vt<bool>(m,false));
       vt<vt<int>> dis(n,vt<int>(m,IMF));
       dis[sn][sm]=0;
       while(!res.empty()){
        auto[nn,nm,nd]=res.top();
        res.pop();
        if(vst[nn][nm]) continue;
        vst[nn][nm]=true;
        for(int i=0;i<4;i++){
            int nx=nn+dx[i];
            int ny=nm+dy[i];
            if(nx>=0 && nx<n && ny>=0 && ny<m){
                if(dis[nx][ny]>op[nx][ny]+nd){
                    dis[nx][ny]=op[nx][ny]+nd;
                    res.push({nx,ny,dis[nx][ny]});
                }
            }
        }
       }
        if(dis[fn][fm]>=h) cout<<"No"<<endl;
       else cout<<"Yes"<<endl;
    }
}