Untitled
unknown
c_cpp
2 years ago
1.3 kB
2
Indexable
#include <stdio.h> #include <limits.h> char map[505][505]; int ch[505][505] = {0}; int n, r, c, tmp = 0; int ans = INT_MAX; int di[4] = {1,0,-1,0}; int dj[4] = {0,1,0,-1}; void maze(int i, int j, int cnt){ //printf("i=%d j=%d\n", i, j); if(map[i][j] == 'F' && cnt < ans){ ans = cnt; tmp = 1; return; } if(cnt > ans && map[i][j] != 'F') return; for(int k = 0; k < 4; k++){ if(i+di[k]<r && i+di[k]>=0 && j+dj[k]<c && j+dj[k]>=0){ if((map[i+di[k]][j+dj[k]] == '$' || map[i+di[k]][j+dj[k]] == 'F') && ch[i+di[k]][j+dj[k]] == 0){ ch[i+di[k]][j+dj[k]] = 1; maze(i+di[k], j+dj[k], cnt+1); ch[i+di[k]][j+dj[k]] = 0; } } } } int main(){ scanf("%d", &n); for(int i = 0; i < n; i++){ int posi, posj; scanf("%d%d", &r, &c); for(int m = 0; m < r; m++){ for(int n = 0; n < c; n++){ scanf(" %c", &map[m][n]); if(map[m][n] == 'S'){ posi = m; posj = n; } } } maze(posi, posj, 0); if(tmp == 0) printf("-1\n"); else printf("%d\n", ans); ans = INT_MAX, tmp = 0; } }
Editor is loading...