Untitled

#include <stdio.h>
#include <string.h>

int n, m, found = 0, cnt = 0;
int di[4] = {1, -1, 0, 0};
int dj[4] = {0, 0, -1, 1};
char map[1005][1005];
int check[1005][1005] = {0};
int Ti[1005], Tj[1005];

void dfs(int posi, int posj){
    if(found == 1) return;
    if(posi == n-1 && posj == m-1){
        found = 1;
        return;
    }
    for(int i = 0; i < 4; i++){
        int ni = posi + di[i];
        int nj = posj + dj[i];
        if(ni < 0  || ni >= n || nj < 0 || nj >= m || check[ni][nj] == 1) continue;
        if(map[ni][nj] != '#'){
            check[ni][nj] = 1;
            dfs(ni, nj);
        }
        if(found == 1) return;
    }
    if(map[posi][posj] == 'T'){
        for(int i = 0; i < cnt; i++){
            if(check[Ti[i]][Tj[i]] == 0){
                check[Ti[i]][Tj[i]] = 1;
                dfs(Ti[i], Tj[i]);
            }
            if(found == 1) return;
        }
    }
}
int main(){
    int t;
    scanf("%d", &t);
    for(int k = 0; k < t; k++){
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                scanf(" %c", &map[i][j]);
                if(map[i][j] == 'T'){
                    Ti[cnt] = i;
                    Tj[cnt] = j;
                    cnt++;
                }
            }
        }
        check[0][0] = 1;
        dfs(0, 0);
        if(found == 0) printf("No\n");
        else printf("Yes\n");
        found = 0, cnt = 0;
        memset(map, '\0', sizeof(map));
        memset(check, 0, sizeof(check));
    }
}