题解 | 小红勇闯地下城

#include <iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int n,m,h;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void dfs(int x,int y,vector<vector<int>>&dp,vector<vector<int>>&a,int fax,int fay)
{
    for(int i=0;i<4;i++)
    {
        int x1=x+dx[i],y1=y+dy[i];
        if(x+dx[i]<=0||x+dx[i]>n||y+dy[i]<=0||y+dy[i]>m||(x1==fax&&y1==fay))
        {
            continue;
        }
        if(dp[x1][y1]<dp[x][y]-a[x1][y1])
        {
            dp[x1][y1]=dp[x][y]-a[x1][y1];
            dfs(x1,y1,dp,a,x,y);
        }
        
    }
}
int main() 
{
    int q;
    cin>>q;
    while(q--)
    {
        cin>>n>>m>>h;
        vector<vector<int>>a(n+2,vector<int>(m+2,0));
        vector<vector<int>>dp(n+2,vector<int>(m+2,-1));
        int xs,ys,xt,yt;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                 char x;
                cin>>x;
                if(x=='S')
                {
                   xs=i;
                   ys=j;
                   dp[i][j]=h;
                    continue;
                }
                if(x=='T')
                {
                   xt=i;
                   yt=j;
                   continue;
                }
                a[i][j]=(long)(x-'0');
            }
        
        }
        dfs(xs,ys,dp,a,-1,-1);
        if(dp[xt][yt]>0)
        {
            cout<<"Yes"<<endl;
        }
        else {
        cout<<"No"<<endl;
        }
    }
}
// 64 位输出请用 printf("%lld")