問題描述 給定一個R行C列的地圖，地圖的每一個方格可能是'#', '+', '-', '|', '.', 'S', 'T'七個字符中的一個，分別表示如下意思：
　　'#': 任何時候玩家都不能移動到此方格；
　　'+': 當玩家到達這一方格后，下一步可以向上下左右四個方向相鄰的任意一個非'#'方格移動一格；
　　'-': 當玩家到達這一方格后，下一步可以向左右兩個方向相鄰的一個非'#'方格移動一格；
　　'|': 當玩家到達這一方格后，下一步可以向上下兩個方向相鄰的一個非'#'方格移動一格；
　　'.': 當玩家到達這一方格后，下一步只能向下移動一格。如果下面相鄰的方格為'#'，則玩家不能再移動；
　　'S': 玩家的初始位置，地圖中只會有一個初始位置。玩家到達這一方格后，下一步可以向上下左右四個方向相鄰的任意一個非'#'方格移動一格；
　　'T': 玩家的目標位置，地圖中只會有一個目標位置。玩家到達這一方格后，可以選擇完成任務，也可以選擇不完成任務繼續移動。如果繼續移動下一步可以向上下左右四個方向相鄰的任意一個非'#'方格移動一格。
　　此外，玩家不能移動出地圖。
　　請找出滿足下面兩個性質的方格個數：
　　1. 玩家可以從初始位置移動到此方格；
　　2. 玩家不可以從此方格移動到目標位置。 輸入格式 輸入的第一行包括兩個整數R 和C，分別表示地圖的行和列數。(1 ≤ R, C ≤ 50)。
　　接下來的R行每行都包含C個字符。它們表示地圖的格子。地圖上恰好有一個'S'和一個'T'。 輸出格式 如果玩家在初始位置就已經不能到達終點了，就輸出“I'm stuck!”（不含雙引號）。否則的話，輸出滿足性質的方格的個數。 樣例輸入 5 5
--+-+
..|#.
..|##
S-+-T
####. 樣例輸出 2 樣例說明 如果把滿足性質的方格在地圖上用'X'標記出來的話，地圖如下所示：
　　--+-+
　　..|#X
　　..|##
　　S-+-T
　　####X —————————————————————————————————————————————————————————————————————— http://www.cnblogs.com/Ritchie/p/6141438.html 兩次 DFS ，一次判斷通否，并將走過的點標記， ，一次從終點出發往回走 ， 每次需要（逆著）判讀 前一點是否能到當前點 1 #include<iostream> 2 #include<vector> 3 using namespace std; 4 int vis[55][55]={0}; 5 6 int ans =0; 7 8 int R,C; 9 10 //vector<vector<char> >v; // 定義 大 小 11 12 char v[53][53]={0}; 13 14 int s_i,s_j,t_i,t_j; 15 16 void dfs1(int i,int j) 17 { 18 if (vis[i][j]==1 || i<0 || i>=R || j<0 || j>=C || v[i][j]=='#')return ; 19 20 vis[i][j] = 1; // 不 用再置 為 0 ！！ 21 22 if (v[i][j]=='+') 23 { 24 dfs1(i-1,j); 25 dfs1(i+1,j); 26 dfs1(i,j+1); 27 dfs1(i,j-1); 28 } 29 30 else if (v[i][j]=='-') 31 { 32 dfs1(i,j-1); 33 dfs1(i,j+1); 34 } 35 36 else if (v[i][j]=='|') 37 { 38 dfs1(i+1,j); 39 dfs1(i-1,j); 40 } 41 42 else if (v[i][j]=='.') 43 { 44 dfs1(i+1,j); 45 } 46 47 } 48 49 50 bool hefa(int i,int j) 51 { 52 if (i<0 || i>=R || j<0 || j>=C)return false; 53 return true; 54 } 55 56 57 void dfs2(int i,int j) 58 { 59 if ( v[i][j]=='#' || vis[i][j]==2)return ; 60 //if(v[i][j]=='#'||i<0||i>=R||j<0||j>=C||vis[i][j]==2) return; 61 62 vis[i][j]=2; 63 64 // cout<<"--i,j "<<i<<" "<<j<<endl; 65 66 if ( hefa(i,j-1) && (v[i][j-1]=='-' || v[i][j-1]=='+')) 67 { 68 dfs2(i,j-1); 69 } 70 71 if (hefa(i,j+1) && (v[i][j+1]=='-' || v[i][j+1]=='+')) 72 { 73 dfs2(i,j+1); 74 } 75 76 if ( hefa(i+1,j) && (v[i+1][j]=='|' || v[i+1][j]=='+')) 77 { 78 dfs2(i+1,j); 79 } 80 81 if ( hefa(i-1,j) && (v[i-1][j]=='.'|| v[i-1][j]=='+' || v[i-1][j]=='|')) 82 { 83 dfs2(i-1,j); 84 } 85 86 87 } 88 89 int main() 90 { 91 92 cin>>R>>C; 93 // v.resize(R); 94 // for (int i=0;i<C;i++)v[i].resize(C); 95 96 97 for (int i=0;i<R;i++) 98 { 99 for (int j =0;j<C;j++) 100 { 101 char s; 102 cin>>s; 103 104 v[i][j]=s; 105 if (s=='S') 106 { 107 s_i = i; 108 s_j = j; 109 v[i][j] = '+'; 110 } 111 if (s=='T') 112 { 113 t_i = i; 114 t_j = j; 115 v[i][j] = '+'; 116 } 117 } 118 } 119 120 dfs1(s_i,s_j); 121 122 // for (int i=0;i<R;i++) 123 // { 124 // for (int j=0;j<C;j++)cout<<vis[i][j]<<" "; //cout<<v[i][j]; //cout<<vis[i][j]<<" "; 125 // cout<<endl; 126 // } 127 128 129 if (vis[t_i][t_j]==1) 130 { 131 dfs2(t_i,t_j); 132 for (int i=0;i<R;i++) 133 { 134 for (int j=0;j<C;j++) 135 { 136 if (vis[i][j]==1) 137 { 138 // cout<<"i,j "<<i<<" "<<j<<endl; 139 ans++; 140 } 141 } 142 } 143 cout<<ans<<endl; 144 } 145 else cout<< "I'm stuck!"<<endl; 146 147 return 0; 148 }

?

轉載于:https://www.cnblogs.com/wuxiaotianC/p/9503915.html

總結

以上是生活随笔為你收集整理的201312-5 I’m stuck!的全部內容，希望文章能夠幫你解決所遇到的問題。

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