Untitled
unknown
plain_text
2 years ago
1.9 kB
5
Indexable
#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; }
Editor is loading...