TopCoder

Thumb coevr
Kevin_Zhang
\(I\ want\ to\ be\ better!\ But\ how.....\)

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

9.5% (2/21)

Description

平衡球 Ballance 出了隱藏的第十四關,出現條件是完整吃下第一到十三關中,

所有的加分和 1UP 達成「絕對貪婪」(Absolutely Complete Greedy,ACG)。

它的玩法是這樣的:現在有一堆交錯的單軌組成許多雙軌,球可以走在任一雙軌上,

但有特殊設計以致無法使用 shortcut,只能在另一雙軌上轉彎。

現在上面有許多的加分,雖然你高興也可以慢慢地吃。

不過正有 Greedy 神人邀你比賽最高得分過關,由於時間減少時分數會下降,

因此為達最高分數你必須以最少的時間花費吃完所有加分才有可能勝利。

為此你必須先找出最佳的食法,現在給你地圖決定吃完所有加分要花幾秒。

加分不會給你太多,但地圖不小,因此要拿高分相當地不容易。

另,假設轉彎需額外花費一秒鐘。

Input Format

輸入含多組測試資料,每組測試資料包含兩正整數 $m$、$n$,皆小於 $101$,

表示有$m$列、$n$行的單軌(詳細格式請參考Sample Input)。

$S$ 表起點,$G$ 表加分,$E$ 表終點。

Output Format

輸出食完所有加分並到達終點之最小時間花費。

Sample Input

2 3
 --- --- ---
| S |   | E |
 --- --- ---
|   | G |   |
 --- --- ---

Sample Output

6

Hints

Akira說:經實驗證實此題的每組測資裡最多會有12個加分。
ggm  說:經實驗證實此題轉彎不管是轉180度或者90度都是一單位時間。

Problem Source

原TIOJ1301 / TFcis9 留社考(prob 7)。Problem Setter:sa072686。

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 262144 2