>author: Utin

## Question

地獄豬要從溫泉出發支援團戰，但是他非常懶惰，請幫他算出他最少要走幾步才能到達團戰現場。

### Input
第一列有兩個整數 R, C，分別代表迷宮的高度及寬度
接著會有 R 列 C 行的字元代表地圖，包含 . # S E
'.' 是可以走的路
'#' 是牆壁
'S' 是起點
'E' 是終點

### Output
請輸出從起點到終點最短的距離

### Constraint
5 <= R, C <= 10

### Sample Input

6 7
#######
##S...#
#...#.#
#.##E.#
#.....#
#######

### Sample Output

6

## 作法
用遞迴做深度優先搜尋

## 常見問題
- scanf 記得取址
- 請確定沒有進入無限遞迴
- 注意遞迴終止條件
- 若小隊員前面還沒寫完的話叫他先寫前面的

## 解法

#include <stdio.h>
#include <limits.h> // 為了要用 INT_MAX，可以用 -1 取代這個做法

int  R, C, Start[2], min_distance = INT_MAX;
char map[10001][10001]; // 1 <= R, C <= 10000

void walk(int row, int col, int distance);

int main() {

    // get the range of map
    scanf("%d %d", &R, &C);

    // get the map and the index of start
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf(" %c", &map[i][j]);
            if (map[i][j] == 'S') {
                Start[0] = i;
                Start[1] = j;
            }
        }
    }

    // recursion
    walk(Start[0], Start[1], 0);

    // output
    printf("%d\n", min_distance == INT_MAX ? 0 : min_distance);
	
}

void walk(int row, int col, int distance) {

    // more than the result we have counted before
    if (distance > min_distance) return;

    // reach the end point
    if (map[row][col] == 'E') {
        min_distance = distance;
        return;
    }

    // try four directions
    for (int i = -1; i <= 1; i += 2) {
        for (int j = 0; j <= 1; j++) {
            if (map[row + i * j][col + i * (1 - j)] != '#') {
                map[row][col] = '#';
                walk(row + i * j, col + i * (1 - j), distance + 1);
                map[row][col] = '*';
            }
        }
    }
    
}