TopCoder

User's AC Ratio

82.2% (37/45)

Submission's AC Ratio

27.1% (54/199)

Description

中秋節的時候有人在森林中烤肉,一不小心就釀成了火災,火勢非常猛烈,如果某個區域原本沒有著火,但是相鄰的區域著火了,那麼下一分鐘這個區域也會被火勢波及。你很不幸的身處於著火的森林中,不過好加在你隨身帶了筆記型電腦,而且你恰好有這個森林地圖的資料。由廣播得知,火勢於第1分鐘發生於起火點F,而現在已經是第T分鐘了。你的位置在S處,標記E的位置代表安全的避難所,並且有直升機場可以搭乘直升機避難。地圖上標著‘*’的地方代表不可通行的區域,‘.’則是代表可以通過的區域。時間緊迫!你得趕緊找安全的逃生路線!

座標化的森林的地圖是一個長17單位、寬10單位的一片土地,詳細狀況如下:

*****************
*...*.......**..*
**..*....*.*.*..*
*......*.**.**.**
*..**...**..**.**
**.....**..*.*..*
*....*..........*
*.....****.*...**
****.*.*........*
*****************

左上角的位置為(0,0),右下角的位置為(9,16)。你每分鐘可以從一個區域移動至相鄰的區域(在這裡所有的相鄰都不包含對角線方向)。現在給定F,T之值以及S,E的位置,請你求出從S到E的最短時間。

Input Format

第一行有兩個正整數FX,FY ,代表起火點F的座標。
第二行有一個正整數T(1<=T<=1,000),代表已經歷時間。
第三行有四個正整數SX,SY,EX,EY,代表你所在的位置以及安全避難所的位置。
你可以假設F,S,E皆位於可通行處。且避難所不會著火,F,S,E互不重疊。

Output Format

若可以安全逃離,請輸出從S到E的最短時間。若你發現身陷火場,或者你根本無法到達避難所的時候,請輸出 “Help!”。

Sample Input

1 1
3
4 1 3 3

Sample Output

9

Hints

Problem Source

原TIOJ1013 / 95建中資訊培訓模擬試題一(Prob 5)

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536