运用深度优先搜索求路径数问题

代码如下

#include <bits/stdc++.h>
using namespace std;
int t;
int n,m;
int mark[505][505];
int dp[505][505];
char a[505][505];
bool flag=false;
int b[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int beginx,beginy,endx,endy;
void dfs(int x,int y){
    if(x==endx||y==endy){
        flag=true;
        return;
    }
    for(int i=0;i<4;i++){
        int x1=x+b[i][0];
        int y1=y+b[i][1];
        if(x1<1||x1>n||y1<1||y1>m)
            continue;
        if(a[x1][y1]=='.'&&mark[x1][y1]==0||a[x1][y1]=='t'&&mark[x1][y1]==0){
            mark[x1][y1]=1;
            dfs(x1,y1);
        }
        if(flag){
            return;
        }
    }
}
int main ()
{
    cin>>t;
    while(t--){
        cin>>n>>m;
        flag=false;
        memset(a,0,sizeof(a));
        memset(mark,0,sizeof(mark));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
                if(a[i][j]=='s'){
                    beginx=i;
                    beginy=j;
                }
                if(a[i][j]=='t'){
                    endx=i;
                    endy=j;
                }
            }
        }
        dfs(beginx,beginy);
        if(flag)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}