# 11291 - Mouse Maze
>author: Utin
###### tags: `recursion`

---

## Brief
See the code below

## Solution 0

#include <stdio.h>
#include <limits.h>

int start[2]; //起點座標
int r, c;
int min_sum = INT_MAX;
char table[501][501]; //迷宮

void run(int index_i, int index_j, int sum);
int check(int index_i, int index_j); //檢查下一步是否能走
int min(int a, int b); //找>0的最小值，若無則return 0

int main() {
    int n;
    scanf("%d", &n);
    for(int t = 0; t < n; t++) {
        scanf("%d %d", &r, &c);
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                scanf("\r%c", &table[i][j]);
                //存起點位址
                if(table[i][j] == 'S') {
                    start[0] = i;
                    start[1] = j;
                }
            }
        }

        run(start[0], start[1], 0);

        //輸出
        if(min_sum == INT_MAX) printf("%d\n", -1); //到不了要輸出-1
        else printf("%d\n", min_sum);

        //還原
        min_sum = INT_MAX;
    }
}

void run(int index_i, int index_j, int sum) {
    if(sum > min_sum) return;

    else if(table[index_i][index_j] == 'F') {
        if(min_sum > sum) min_sum = sum;
    }

    else {
        //設成走過
        table[index_i][index_j] = '#';

        if(check(index_i+1, index_j)) run(index_i+1, index_j, sum+1);
        if(check(index_i-1, index_j)) run(index_i-1, index_j, sum+1);
        if(check(index_i, index_j+1)) run(index_i, index_j+1, sum+1);
        if(check(index_i, index_j-1)) run(index_i, index_j-1, sum+1);

        //還原成沒走過
        table[index_i][index_j] = '$';
    }
}

//檢查下一步是否能走
int check(int index_i, int index_j) {
    if(index_i >= 0 && index_i < r && index_j >= 0 && index_j < c) {
        if(table[index_i][index_j] == '$' || table[index_i][index_j] == 'F') {
            return 1;
        }
    }
    return 0;
}
// By Utin

## Reference