Untitled

#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;
    }
}