Hakka's Maze

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
1.6 kB
1
Indexable
Never
//Hakka's Maze

#include <stdio.h>
#include <string.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, cnt = 0;

void dfs(int posi, int posj){
    if(found == 1) return;
    if(posi == n && posj == m) found = 1;
    check[posi][posj] = 1;
    for(int k = 0; k < 4; k++){
        int ni = posi + di[k];
        int nj = posj + dj[k];
        if(map[ni][nj] != '#' && check[ni][nj] == 0){
            if(ni<=0 || ni>n || nj<=0 || nj>m) continue;
            dfs(ni, nj);
            if(found == 1) return;//重要!!在這裡加found可以讓他少跑k個迴圈
        }
        if(map[posi][posj] == 'T'){
            for(int i = 0; i < cnt; i++){
                if(check[posi_T[i]][posj_T[i]] == 0){
                    if(found == 1) return;
                    dfs(posi_T[i], posj_T[i]);
                }
            }
        }
    }
}
int main(){

    int t;
    scanf("%d", &t);
    
    for(int i = 0; i < t; i++){
        found = 0, cnt = 0;
        scanf("%d%d", &n, &m);
        memset(check, 0, sizeof(check));
        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(1, 1);

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