Gold King勇闯八卦图·题解

思路：
深搜，问是否能正好在第 $c$ 步从出发点到终点。
代码：

#include<bits/stdc++.h>
using namespace std;

int t,n,m,c,fx,fy,sx,sy,zx[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
bool flag,map_[10][10],vis[10][10];
char cc;

void dfs(int xx,int yy,int cnt){
    if(xx==sx&&yy==sy&&cnt==c){flag=1;}
    if(cnt>c){return ;}
    for(int i=0;i<4;i++){
        int xxx=xx+zx[i][0],yyy=yy+zx[i][1];
        if(vis[xxx][yyy]==0&&map_[xxx][yyy] && xxx>=0&&xxx<n && yyy>=0&&yyy<m){
            vis[xxx][yyy]=1;
            dfs(xxx,yyy,cnt+1);
            vis[xxx][yyy]=0;
        }
    }
}

int main(){
    scanf("%d",&t);;
    while(t--){
        scanf("%d %d %d",&n,&m,&c);
        for(int i=0;i<n;i++) for(int j=0;j<m;j++){
            cin>>cc;
            if(cc=='.') map_[i][j]=1;
            else if(cc=='X') map_[i][j]=0;
            else if(cc=='S' || cc=='T'){
                map_[i][j]=1;
                if(cc=='S') fx=i,fy=j;
                else sx=i,sy=j;
            }
        }
        memset(vis,0,sizeof vis);
        flag=0;
        dfs(fx,fy,0);
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}