Untitled

 avatar
unknown
c_cpp
3 years ago
1.3 kB
8
Indexable
//Hakka's Maze

#include <stdio.h>

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

int dfs(int posi, int posj){
    
    for(int k = 0; k < 4; k++){
        if(posi == n && posj == m) return 1; 
        if(posi+di[k]<0 || posi+di[k]>n || posj+dj[k]<0 || posj+dj[k]>m) continue;
        if(map[posi+di[k]][posj+dj[k]] == '*' && check[posi+di[k]][posj+dj[k]] == 0){
            printf("posi = %d, posj = %d", posi, posj);
            check[posi+di[k]][posj+dj[k]] = 1;
            dfs(posi+di[k], posj+dj[k]);
            check[posi+di[k]][posj+dj[k]] = 0;
        }
    }
    return 0;
}
int main(){

    int t;
    
    scanf("%d", &t);
    for(int i = 0; i < t; i++){
        int posi = 1, posj = 1;
        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';
            }
        }
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= m; k++){
                scanf(" %c", &map[j][k]);
            }
        }
        if(dfs(posi, posj) == 1) printf("Yes\n");
        else printf("No\n");
    }
}
Editor is loading...