Untitled

#include<stdio.h>

char zoo[1000][1000];
int intzoo[1001][1001], step[1001][1001];                                  // intzoo 將zoo換成0, 1，0-->有路 1-->障礙物
                                                                           // step 計算步數/判斷有沒有走過  !0為有
int min(int a, int b);

int main(){

    int r, c,s[2], m[2], tmp;
    int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    scanf("%d %d\n", &r, &c);

    for(int i=0; i<r; i++){                                                 // 輸入
        for(int j=0; j<c; j++){
            scanf(" %c", &zoo[i][j]);
            if(zoo[i][j] == 'S') s[0] = i, s[1]= j;
            if(zoo[i][j] == 'M') m[0] = i, m[1] = j;
            if(zoo[i][j] == 'o' || zoo[i][j] == '^') intzoo[i][j] = 1;
        }
        if(i < r-1) scanf(" ");
    }

    step[s[0]][s[1]] = 1;
    while(!step[m[0]][m[1]]){                                              //第一個碰到M的為最少步數 --> M != 0跳出 
        for(int i=0; i<r; i++){                                            // 細菌走法 狂刷猛刷
            for(int j=0; j<c; j++){
                
                for(int k=0; k<4; k++){
                    if(intzoo[i+dir[k][0]][j+dir[k][1]] == 0 && step[i][j]){    // 先判下一步沒有走過 再看這個點要有走過(你不能瞬間移動)
                        tmp = step[i][j] + 1;
                        step[i+dir[k][0]][j+dir[k][1]] = step[i+dir[k][0]][j+dir[k][1]] ? min(step[i+dir[k][0]][j+dir[k][1]], tmp) : tmp;  // 若該位置已經被走過 判最小步數
                    }
                }
            }
        }
    }
    printf("%d\n", step[m[0]][m[1]]-1);                                   //總步數-1 (依題意S為第0步)
}

int min(int a, int b){
    a = (a<b) ? a : b;
    return a;
}