解题步骤：DFS或者BFS裸题，记录好障碍和边界，然后从起点搜索判断能否走到终点

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505;
const int dir[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int n, m;
string mz[maxn];
bool flag = 0;
bool vis[maxn][maxn];
struct node {
    int x, y;
};

bool check(node now) {
    return now.x < 0 || now.x >= n || now.y < 0 || now.y >= m || vis[now.x][now.y];
}

void dfs(node now) {
    if (check(now)) return;
    vis[now.x][now.y] = 1;
    if (mz[now.x][now.y] == 't') {
        flag = 1;
        return;
    }
    node nex = now;
    for (int i = 0; i < 4; ++i) {
        nex.x = now.x + dir[i][0], nex.y = now.y + dir[i][1];
        dfs(nex);
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        memset(vis, 0, sizeof vis);
        flag = 0;
        cin >> n >> m;
        for (int i = 0; i < n; ++i) {
            cin >> mz[i];
            for (int j = 0; j < m; ++j)
                if (mz[i][j] == 'x') vis[i][j] = 1;
        }
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (mz[i][j] == 's') {
                    dfs(node{i, j});
                    goto LOOP;
                }
    LOOP:
        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    // system("pause");
    return 0;
}