簡單的最短路 BFS DFS都可以實現(xiàn)（BFS應該會更快一點吧）

其中輸入的N、M、T中，N是列，M是行，而不是和大多數題目一樣，N是行，M是列

另外，類中不要亂放常量，類中不要直接為類變量賦初值（不是所有編譯器都承認貌似~）

1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 #define REP(n) for(int o=0;o<n;o++) 7 8 const int maxn = 25; 9 const int delta[4] = {0,0,1,-1}; 10 11 class LOVE { 12 private: 13 int N,M,T; 14 int x1,y1,x2,y2; 15 bool visited[maxn][maxn];//是否已訪問過該位置 16 char map[maxn][maxn];//地圖 17 int ans;//結果 18 19 20 void dfs(int x,int y,int l) { 21 if(x < 0 || y < 0 || x >= M || y >= N || 22 visited[x][y] == true || map[x][y] == '*') 23 return; 24 if(x == x2&&y == y2) 25 ans = l; 26 27 visited[x][y] = true; 28 29 for(int i = 0;i < 4;i++) 30 dfs(x + delta[i],y + delta[3 - i],l + 1); 31 32 } 33 34 public: 35 bool Do() { 36 scanf("%d%d%d",&N,&M,&T); 37 //測試數據結束 38 if(N == 0 && M == 0 && T == 0) 39 return false; 40 //輸入地圖 41 for(int i = 0;i < M;i++) { 42 for(int j = 0;j < N;j++) { 43 char temp; 44 scanf("\n%c\n",&temp); 45 if(temp == 'S') { 46 x1 = i; 47 y1 = j; 48 temp = '.'; 49 } 50 if(temp == 'P') { 51 x2 = i; 52 y2 = j; 53 temp = '.'; 54 } 55 map[i][j] = temp; 56 } 57 } 58 59 //輸出地圖 60 /* 61 for(int i = 0;i < M;i++) { 62 for(int j = 0;j < N;j++) 63 printf("%c",map[i][j]); 64 printf("\n"); 65 } 66 printf("\n"); 67 */ 68 69 //初始化 70 ans = -1; 71 memset(visited,false,sizeof(visited)); 72 //dfs尋求最短路（用bfs應該會更快點，不過數據小，就不改了） 73 dfs(x1,y1,0); 74 75 /* 76 for(int i = 0;i < M;i++) { 77 for(int j = 0;j < N;j++) 78 printf("%d",visited[i][j]); 79 printf("\n"); 80 } 81 printf("\n"); 82 */ 83 84 printf("%s\n",ans == -1 || ans > T ? "NO" : "YES"); 85 86 return true; 87 } 88 }; 89 90 91 92 int main() { 93 LOVE LIVE; 94 while(LIVE.Do()); 95 return 0; 96 }

?

轉載于:https://www.cnblogs.com/ohyee/p/5246445.html

總結

以上是生活随笔為你收集整理的AOJ 6.Hero In Maze的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。