TopCoder

abcabcabc
有人要寫 p6 嗎 > <

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

Description

完整題本 PDF:中文英文馬來文

作為一名被派遣至敵軍後方的菁英特種部隊成員,你的任務是潛入敵方領地、取得關鍵情報並安全撤離:

  • 從基地($\texttt{S}$)出發,
  • 抵達情報點($\texttt{T}$)並取得機密資料,
  • 最後前往撤離點($\texttt{E}$)完成撤離。

戰場由牆壁與通路組成的迷宮構成。你每次可以向上、下、左、右移動一步,但不能斜向移動,也不能穿越牆壁。

請計算從基地($\texttt{S}$)出發,經過情報點($\texttt{T}$),最終到達撤離點($\texttt{E}$)所需的最少步數。
若不可能完成任務,回報無法達成。

Input Format

第一行包含兩個以空格分隔的整數 $n$ 和 $m$,代表迷宮的行數與列數。
接下來的 $n$ 行中,每行一個長度為 $m$ 的字串,代表迷宮的每一行,其中:

  • $\texttt{\#}$ 代表牆壁,
  • $\texttt{.}$ 代表通路,
  • $\texttt{S}$ 代表基地/起點,
  • $\texttt{T}$ 代表情報點,
  • $\texttt{E}$ 代表撤離/出口點。


  • $4 \leq n, m \leq 1000$。
  • 保證迷宮中恰有一個基地($\texttt{S}$)、一個情報點($\texttt{T}$)和一個撤離點($\texttt{E}$)。
  • 迷宮的最外層邊界全部由牆壁($\texttt{\#}$)組成。

Output Format

輸出一個整數,表示從基地($\texttt{S}$)經過情報點($\texttt{T}$)到達撤離點($\texttt{E}$)所需的最少步數。
若不可能完成任務,請輸出 $\texttt{-1}$。

Sample Input 1

5 7
#######
#S...E#
###.#.#
#T....#
#######

Sample Output 1

12

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 2097152 65536
1 1000 2097152 65536
2 1000 2097152 65536
3 1000 2097152 65536
4 1000 2097152 65536
5 1000 2097152 65536
6 1000 2097152 65536
7 1000 2097152 65536
8 1000 2097152 65536
9 1000 2097152 65536
10 1000 2097152 65536
11 1000 2097152 65536
12 1000 2097152 65536
13 1000 2097152 65536
14 1000 2097152 65536
15 1000 2097152 65536
16 1000 2097152 65536
17 1000 2097152 65536
18 1000 2097152 65536
19 1000 2097152 65536
20 1000 2097152 65536
21 1000 2097152 65536
22 1000 2097152 65536
23 1000 2097152 65536
24 1000 2097152 65536
25 1000 2097152 65536
26 1000 2097152 65536
27 1000 2097152 65536
28 1000 2097152 65536
29 1000 2097152 65536
30 1000 2097152 65536
31 1000 2097152 65536
32 1000 2097152 65536
33 1000 2097152 65536
34 1000 2097152 65536
35 1000 2097152 65536
36 1000 2097152 65536
37 1000 2097152 65536
38 1000 2097152 65536