Untitled

#include <stdio.h>
#include <string.h>
int n, m, found = 0, check[1005][1005][3];
char map[1005][1005];
int di[4] = {0, 0, 1,-1};
int dj[4] = {1, -1,0, 0};

void dfs(int posi, int posj, int step){
    if(posi == n && posj == m){
        found = 1;
        return;
    }
    if(found == 1) return;
    for(int i = 0; i < 4; i++){
        int ni = posi + di[i];
        int nj = posj + dj[i];
        if((step+1)%3 == 1 && map[ni][nj] == 'A') return;
        else if((step+1)%3 == 2 && map[ni][nj] == 'B') return;
        else if((step+1)%3 == 0 && map[ni][nj] == 'C') return;
        if(map[ni][nj] != '#' && check[ni][nj][(step+1)%3] == 0){
            if(ni <= 0 || ni > n || nj <= 0 || nj > m) continue;
            check[ni][nj][(step+1)%3] = 1;
            dfs(ni, nj, step+1);
        }
    }
}

int main(){
    int t;
    scanf("%d", &t);
    for(int k = 0; k < t; k++){
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                scanf(" %c", &map[i][j]);
            }
        }
        dfs(1, 1, 0);
        if(found == 1)printf("Yes\n");
        else printf("No\n");
        memset(map, '\0', sizeof(map));
        found = 0;
    }
}