試題名稱： I’m stuck!
時間限制： 1.0s
記憶體限制： 256.0MB
問題描述：
問題描述 給定一個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
解題思路:
1、深度周遊，選擇隊列。
2、方向和圖形符号互相對應。
根據标準代碼分析（java）：
1 package ccf_text2013_12;
2
3 import java.util.*;
4 /**
5 * I'm stuck!
6 * 給定一個R行C列的地圖，地圖的每一個方格可能是'#', '+', '-', '|', '.', 'S', 'T'七個字元中的一個，分别表示如下意思：
7 '#': 任何時候玩家都不能移動到此方格；
8 '+': 當玩家到達這一方格後，下一步可以向上下左右四個方向相鄰的任意一個非'#'方格移動一格；
9 '-': 當玩家到達這一方格後，下一步可以向左右兩個方向相鄰的一個非'#'方格移動一格；
10 '|': 當玩家到達這一方格後，下一步可以向上下兩個方向相鄰的一個非'#'方格移動一格；
11 '.': 當玩家到達這一方格後，下一步隻能向下移動一格。如果下面相鄰的方格為'#'，則玩家不能再移動；
12 'S': 玩家的初始位置，地圖中隻會有一個初始位置。玩家到達這一方格後，下一步可以向上下左右四個方向相鄰的任意一個非'#'方格移動一格；
13 'T': 玩家的目标位置，地圖中隻會有一個目标位置。玩家到達這一方格後，可以選擇完成任務，也可以選擇不完成任務繼續移動。如果繼續移動下一步可以向上下左右四個方向相鄰的任意一個非'#'方格移動一格。
14 此外，玩家不能移動出地圖。
15 請找出滿足下面兩個性質的方格個數：
16 1. 玩家可以從初始位置移動到此方格；
17 2. 玩家不可以從此方格移動到目标位置。
18 * @author Hello stranger
19 *
20 */
21 public class ImStuck2 {
22
23 public static void main(String[] args) {
24
25 new ImStuck2().run();
26 }
27
28 public void run() {
29
30 Scanner fin = new Scanner(System.in);
31
32 int R = fin.nextInt();
33
34 int C = fin.nextInt(); //判斷圖形的行和列
35
36 String first = fin.nextLine(); //跳過輸入的換行（輸入行列之後會打一個換行）
37
38 //System.out.println(first);
39
40 int[][] board = new int[R + 2][C + 2];
41
42 char[][] picture = new char[R][C]; //為了驗證計算出的結果是否在圖形上顯示正确
43
44 int rowStart = 0, colStart = 0, rowEnd = 0, colEnd = 0; //起點和終點所在的行列
45
46 for (int i = 1; i <= R; ++i) {
47
48 //讀取輸入的圖形标志，并将圖形标志轉化為數字标示并儲存在數組中,關鍵在于這些數字
49 /**
50 * # === 0
51 * - === 5
52 * | === 0xA == 10
53 * + === 0xF == 15
54 * S === 0xF == 15
55 * T === 0xF == 15
56 * . === 0x8 == 8
57 *
58 */
59 String line = fin.nextLine();
60
61 for (int j = 1; j <= C; ++j) {
62
63 char c = line.charAt(j - 1);
64
65 picture[i-1][j-1] = c;
66
67 switch (c) {
68
69 case '#':
70
71 break;
72
73 case '-':
74
75 board[i][j] = 5;
76
77 break;
78
79 case '|':
80
81 board[i][j] = 0xA;
82
83 break;
84
85 case '+':
86
87 case 'S':
88
89 case 'T':
90
91 board[i][j] = 0xF;
92
93 break;
94
95 case '.':
96
97 board[i][j] = 0x8;
98
99 break;
100
101 default:
102
103 break;
104
105 }
106 if (c == 'S') {
107
108 rowStart = i;
109
110 colStart = j; //起點所在的行列
111
112 } else if (c == 'T') {
113
114 rowEnd = i;
115
116 colEnd = j; //終點所在的行列
117 }
118 }
119 }
120 System.out.println("使用者輸入的圖形為：");
121 printCharArray(picture);
122 printNumArray(board);
123 int[] dr = new int[] { 0, -1, 0, 1 }; //行數 同行、上一行（向上）、 同行、 下一行（向下）
124
125 int[] dc = new int[] { 1, 0, -1, 0 }; //列數 下一列（向右）、 同列、上一列（向左）、同列
126
127
128 // Scan 1: find all cells which can reach T
129
130 boolean[][] visited = new boolean[R + 2][C + 2]; //預設均為false
131
132 boolean[][] canReachT = new boolean[R + 2][C + 2]; //預設均為false
133
134 initVisited(visited); //數組邊框為true，中間為false
135
136 canReachT[rowEnd][colEnd] = true;
137
138 visited[rowEnd][colEnd] = true; //重點的值設為true
139
140 Queue<Integer> queue = new LinkedList<Integer>();
141
142 queue.add(rowEnd);
143
144 queue.add(colEnd); //隊列有一個特點就是先進先出，這樣就可以采用深度優先周遊
145
146
147 while (!queue.isEmpty()) {
148
149 int r = queue.remove();
150
151 int c = queue.remove();
152
153 for (int i = 0; i < 4; ++i) {
154
155 int nr = r + dr[i];
156
157 int nc = c + dc[i]; //判斷順序是 向右，向下，向左，向上(四個方向)
158
159 if (visited[nr][nc]) //邊框+已經判定可以到達終點的點
160
161 continue;
162
163 if ((board[nr][nc] & (1 << ((i + 2) % 4))) != 0) {
164
165 /**
166 * 方向 右 下 左 上
167 * i 0 1 2 3
168 * t = (i + 2) % 4 2 3 0 1
169 * x = 1 << t 4 8 1 2
170 * # === 0x0 == 0 & x 0 0 0 0
171 * - === 0x5 == 5 & x 4 0 1 0
172 * | === 0xA == 10 & x 0 8 0 2
173 * + === 0xF == 15 & x 4 8 1 2
174 * S === 0xF == 15 & x 4 8 1 2
175 * T === 0xF == 15 & x 4 8 1 2
176 * . === 0x8 == 8 & x 0 8 0 0
177 *
178 */
179
180 //将上下左右和數字表示的圖示對應起來，如果在這個方向可以走的話，就執行if語句
181
182 canReachT[nr][nc] = true; //這個數組裡面值為false的即為玩家不可以從此方格移動到目标位置。
183
184 queue.add(nr);
185
186 queue.add(nc);
187
188 visited[nr][nc] = true;
189 }
190 }
191 }
192
193 printBealoonArray(visited);
194
195 if (!canReachT[rowStart][colStart]) {
196
197 System.out.println("I'm stuck!");
198
199 return;
200 }
201 // Scan 2: get result 同理
202
203 boolean[][] rCanReach = new boolean[R + 2][C + 2];
204
205 initVisited(visited);
206
207 queue.clear();
208
209 visited[rowStart][colStart] = true;
210
211 rCanReach[rowStart][colStart] = true;
212
213 queue.add(rowStart);
214
215 queue.add(colStart);
216
217 while (!queue.isEmpty()) {
218
219 int r = queue.remove();
220
221 int c = queue.remove();
222
223 for (int i = 0; i < 4; ++i) {
224
225 if ((board[r][c] & (1 << i)) == 0)
226
227 continue;
228
229 int nr = r + dr[i];
230
231 int nc = c + dc[i];
232
233 if (visited[nr][nc])
234
235 continue;
236
237 if (board[nr][nc] == 0)
238
239 continue;
240
241 rCanReach[nr][nc] = true; //這個數組裡面值為true的即為玩家可以從初始位置移動到此方格
242
243 queue.add(nr);
244
245 queue.add(nc);
246
247 visited[nr][nc] = true;
248 }
249 }
250 int result = 0;
251
252 //符合兩個條件的圖所位于的行列
253
254 for (int i = 1; i <= R; ++i) {
255
256 for (int j = 1; j <= C; ++j) {
257
258 if (rCanReach[i][j] && (!canReachT[i][j])){
259
260 ++result;
261
262 picture[i-1][j-1] = 'X';
263
264 }
265
266 }
267 }
268
269 System.out.println("經過計算之後的圖形為：");
270
271 printCharArray(picture);
272
273 System.out.println("滿足條件的位置有 " + result + " 個。");
274 }
275
276 /**
277 * 預先初始化數組的時候多了邊框，因為visited數組預設為false
278 * 此函數的目的是使得visited數組邊框的預設值變為true
279 * 使得visited數組中間的值預設為false
280 * @param visited
281 */
282
283 private void initVisited(boolean[][] visited) {
284
285 int R = visited.length - 2;
286
287 int C = visited[0].length - 2;
288
289 for (int i = 0; i <= R + 1; ++i) {
290
291 visited[i][0] = true;
292
293 visited[i][C + 1] = true;
294 }
295 for (int j = 0; j <= C + 1; ++j) {
296
297 visited[0][j] = true;
298
299 visited[R + 1][j] = true;
300 }
301 for (int i = 1; i <= R; ++i) {
302
303 for (int j = 1; j <= C; ++j) {
304
305 visited[i][j] = false;
306
307 }
308
309 }
310
311 }
312 /**
313 * 列印數組中儲存的值
314 * 在此程式中為 輸出等價于圖形的數字數組
315 * @param queue
316 */
317 public static void printNumArray(int[][] board){
318
319 System.out.println("=======================begin int board array=====================");
320
321 for (int i = 0; i < board.length; ++i) {
322
323 for (int j = 0; j < board[i].length; ++j) {
324
325 System.out.print(board[i][j]+"\t");
326 }
327 System.out.println();
328 }
329 System.out.println("===========================end========================");
330 }
331
332 /**
333 * 列印char數組中儲存的值
334 * 在此程式中為 輸出圖形
335 * @param queue
336 */
337 public static void printCharArray(char[][] picture){
338
339 System.out.println("=======================begin char picture array=====================");
340
341 for (int i = 0; i < picture.length; ++i) {
342
343 for (int j = 0; j < picture[i].length; ++j) {
344
345 System.out.print(picture[i][j]);
346 }
347 System.out.println();
348 }
349 System.out.println("===========================end========================");
350 }
351
352 /**
353 * 列印boolean數組中儲存的值
354 * @param queue
355 */
356 public static void printBealoonArray(boolean[][] visted){
357
358 System.out.println("=======================begin Boolean visted array =====================");
359
360 for (int i = 0; i < visted.length; ++i) {
361
362 for (int j = 0; j < visted[i].length; ++j) {
363
364 System.out.print(visted[i][j]+"\t");
365 }
366 System.out.println();
367 }
368 System.out.println("===========================end========================");
369 }
370 /**
371 * 列印隊列中儲存的值
372 * @param queue
373 */
374 public static void printQueue(Queue<Integer> queue){
375
376 Iterator it = queue.iterator();
377
378 System.out.println("=======================begin queue=====================");
379
380 int i = 0;
381
382 while(it.hasNext()){
383
384 System.out.print(it.next() + "\t");
385
386 if((++i)%2 == 0){
387
388 System.out.println();
389 }
390 }
391 System.out.println("===========================end========================");
392 }
393 } 運作結果如下：
标準代碼如下（java）：
1 package ccf_text2013_12;
2
3 import java.util.*;
4 /**
5 * I'm stuck!
6 * 給定一個R行C列的地圖，地圖的每一個方格可能是'#', '+', '-', '|', '.', 'S', 'T'七個字元中的一個，分别表示如下意思：
7 '#': 任何時候玩家都不能移動到此方格；
8 '+': 當玩家到達這一方格後，下一步可以向上下左右四個方向相鄰的任意一個非'#'方格移動一格；
9 '-': 當玩家到達這一方格後，下一步可以向左右兩個方向相鄰的一個非'#'方格移動一格；
10 '|': 當玩家到達這一方格後，下一步可以向上下兩個方向相鄰的一個非'#'方格移動一格；
11 '.': 當玩家到達這一方格後，下一步隻能向下移動一格。如果下面相鄰的方格為'#'，則玩家不能再移動；
12 'S': 玩家的初始位置，地圖中隻會有一個初始位置。玩家到達這一方格後，下一步可以向上下左右四個方向相鄰的任意一個非'#'方格移動一格；
13 'T': 玩家的目标位置，地圖中隻會有一個目标位置。玩家到達這一方格後，可以選擇完成任務，也可以選擇不完成任務繼續移動。如果繼續移動下一步可以向上下左右四個方向相鄰的任意一個非'#'方格移動一格。
14 此外，玩家不能移動出地圖。
15 請找出滿足下面兩個性質的方格個數：
16 1. 玩家可以從初始位置移動到此方格；
17 2. 玩家不可以從此方格移動到目标位置。
18 * @author Hello stranger
19 *
20 */
21 public class ImStuck {
22 public static void main(String[] args) {
23 new ImStuck().run();
24 }
25
26 public void run() {
27 Scanner fin = new Scanner(System.in);
28 int R = fin.nextInt();
29 int C = fin.nextInt();
30 fin.nextLine();
31 int[][] board = new int[R + 2][C + 2];
32 int rowStart = 0, colStart = 0, rowEnd = 0, colEnd = 0;
33 for (int i = 1; i <= R; ++i) {
34 String line = fin.nextLine();
35 for (int j = 1; j <= C; ++j) {
36 char c = line.charAt(j - 1);
37 switch (c) {
38 case '#':
39 break;
40 case '-':
41 board[i][j] = 5;
42 break;
43 case '|':
44 board[i][j] = 0xA;
45 break;
46 case '+':
47 case 'S':
48 case 'T':
49 board[i][j] = 0xF;
50 break;
51 case '.':
52 board[i][j] = 0x8;
53 break;
54 default:
55 break;
56 }
57 if (c == 'S') {
58 rowStart = i;
59 colStart = j;
60 } else if (c == 'T') {
61 rowEnd = i;
62 colEnd = j;
63 }
64 }
65 }
66 int[] dr = new int[] { 0, -1, 0, 1 };
67 int[] dc = new int[] { 1, 0, -1, 0 };
68 // Scan 1: find all cells which can reach T
69 boolean[][] visited = new boolean[R + 2][C + 2];
70 boolean[][] canReachT = new boolean[R + 2][C + 2];
71 initVisited(visited);
72 canReachT[rowEnd][colEnd] = true;
73 visited[rowEnd][colEnd] = true;
74 Queue<Integer> queue = new LinkedList<Integer>();
75 queue.add(rowEnd);
76 queue.add(colEnd);
77 while (!queue.isEmpty()) {
78 int r = queue.remove();
79 int c = queue.remove();
80 for (int i = 0; i < 4; ++i) {
81 int nr = r + dr[i];
82 int nc = c + dc[i];
83 if (visited[nr][nc])
84 continue;
85 if ((board[nr][nc] & (1 << ((i + 2) % 4))) != 0) {
86 canReachT[nr][nc] = true;
87 queue.add(nr);
88 queue.add(nc);
89 visited[nr][nc] = true;
90 }
91 }
92 }
93 /*
94 * for (int i = 1; i <= R; ++i) { for (int j = 1; j <= C; ++j) { if
95 * (canReachT[i][j]) { System.out.println("i = " + i + ", j = " + j); }
96 * } }
97 */
98 if (!canReachT[rowStart][colStart]) {
99 System.out.println("I'm stuck!");
100 return;
101 }
102 // Scan 2: get result
103 boolean[][] rCanReach = new boolean[R + 2][C + 2];
104 initVisited(visited);
105 queue.clear();
106 visited[rowStart][colStart] = true;
107 rCanReach[rowStart][colStart] = true;
108 queue.add(rowStart);
109 queue.add(colStart);
110 while (!queue.isEmpty()) {
111 int r = queue.remove();
112 int c = queue.remove();
113 for (int i = 0; i < 4; ++i) {
114 if ((board[r][c] & (1 << i)) == 0)
115 continue;
116 int nr = r + dr[i];
117 int nc = c + dc[i];
118 if (visited[nr][nc])
119 continue;
120 if (board[nr][nc] == 0)
121 continue;
122 rCanReach[nr][nc] = true;
123 queue.add(nr);
124 queue.add(nc);
125 visited[nr][nc] = true;
126 }
127 }
128 int result = 0;
129 for (int i = 1; i <= R; ++i) {
130 for (int j = 1; j <= C; ++j) {
131 /*
132 * if (rCanReach[i][j]) { System.out.println("i = " + i +
133 * ", j = " + j); }
134 */
135 if (rCanReach[i][j] && (!canReachT[i][j]))
136 ++result;
137 }
138 }
139 System.out.println(result);
140 }
141
142 private void initVisited(boolean[][] visited) {
143 int R = visited.length - 2;
144 int C = visited[0].length - 2;
145 for (int i = 0; i <= R + 1; ++i) {
146 visited[i][0] = true;
147 visited[i][C + 1] = true;
148 }
149 for (int j = 0; j <= C + 1; ++j) {
150 visited[0][j] = true;
151 visited[R + 1][j] = true;
152 }
153 for (int i = 1; i <= R; ++i) {
154 for (int j = 1; j <= C; ++j) {
155 visited[i][j] = false;
156
157 }
158
159 }
160
161 }
162 } 轉載于:https://www.cnblogs.com/haimishasha/p/5323639.html