Untitled

//Hakka's Maze

#include <stdio.h>

char map[1005][1005];
int check[1005][1005] = {0}, posi_T[1005]={0}, posj_T[1005] = {0};
int di[4] = {1, 0, 0, -1};
int dj[4] = {0, 1, -1, 0};
int n, m, found = 0, posi, posj, cnt = 0;

void dfs(int posi, int posj){
    if(found == 1) return;
    check[posi][posj] = 1;
    for(int k = 0; k < 4; k++){
        if(posi == n && posj == m){
            found = 1;
            return; 
        }
        if(map[posi+di[k]][posj+dj[k]] != '#' && check[posi+di[k]][posj+dj[k]] == 0){
            if(posi+di[k]<=0 || posi+di[k]>n || posj+dj[k]<=0 || posj+dj[k]>m) continue;
            dfs(posi+di[k], posj+dj[k]);
            //check[posi+di[k]][posj+dj[k]] = 0;
        }
        if(map[posi][posj] == 'T'){
            for(int i = 0; i < cnt; i++){
                if(check[posi_T[i]][posj_T[i]] == 0){
                    if(found) return;
                    dfs(posi_T[i], posj_T[i]);
                    //check[posi_T[i]][posj_T[i]] = 0;
                }
            }
        }
    }
}
int main(){

    int t;
    scanf("%d", &t);
    
    for(int i = 0; i < t; i++){
        posi = 1, posj = 1, found = 0, cnt = 0;
        scanf("%d%d", &n, &m);
        for(int j = 0; j < 1005; j++){
            for(int k = 0; k < 1005; k++){
                check[j][k] = 0;
                map[j][k] = '\0';
                posi_T[j] = 0;
                posj_T[j] = 0;
            }
        }
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= m; k++){
                scanf(" %c", &map[j][k]);
                if(map[j][k] == 'T'){
                    posi_T[cnt] = j;
                    posj_T[cnt] = k;
                    cnt++;
                }
            }
        }
        check[1][1] = 1;
        dfs(posi, posj);

        if(found == 1) printf("Yes\n");
        else printf("No\n");
    }
}