q369. 4. 洛聖都逃亡計畫 - 高中生程式解題系統

Content

　　你是洛聖都（Los Santos）最臭名昭著的街頭賽車手，在一場瘋狂的銀行搶案後，你必須甩開瘋狂追捕你的警察，並設法逃到藏身點！
　　洛聖都的街道如同迷宮，某些路段被警方封鎖，而你只能在開放的道路上移動。你需要找到一條路，從你現在的位置 S 開車逃到安全屋 T，避免被警方圍捕！
　　洛聖都是一個 $N×M$ 的城市地圖，由以下符號組成：

. （道路）：你可以自由行駛的街道。
# （封鎖區）：警方封鎖的道路，你無法通過。
S （起點）：你目前的位置。
T （安全屋）：你的目標地點。

你只能沿著上下左右四個方向駕駛（不能斜向移動）。請判斷你是否能從 S 開車到 T，並輸出 "mission passed respect+" 或 "wasted"。

Input

　　第一行包含兩個整數 $N, M$（$1\le N, M\le 1000$）代表城市地圖的大小。
　　接下來的 $N$ 行,每行包含一個長度為 $M$ 的字串，描述整個城市的道路狀況。（保證 S 和 T 各出現恰好一次）

Output

　　若能順利開車到達安全屋，輸出 "mission passed respect+"。
　　若所有道路都被封鎖而無法抵達安全屋，輸出 "wasted"。

Sample Input #1

5 5
S...#
.##.#
...#.
#.#.T
#....

Sample Output #1

mission passed respect+

Sample Input #2

3 3
S##
.#.
##T

Sample Output #2

wasted

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

Hint ：

　　輸出直接複製給的範例就行，自己打容易出錯。

本題共有 $3$ 個子題，每個子題有多筆測資。
第一子題：　$N\times M\le 100$，全部解出可得 $20$ 分。
第二子題：　$N\times M\le 10000$，全部解出可得 $30$ 分。
第三子題：　無其它限制，全部解出可得 $50$ 分。

Authored by ZakAlbert

Tags:

BFS

出處:

113學年度新北新莊高中校內資訊學科能力競賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」