2011年6月12日 星期日

11914 - An Amazing Race


你正參與一項競賽,一開始你處在一座島的岸邊且必須到達指定的目的地,在到達目的地之前必須先經過幾個"中繼點"(checkpoint),最先到達目的地的人贏得比賽。

島上的溫度高達45度,在這樣的高溫環境下一定要喝大量的水才行,但是比賽不允許你帶任何一滴水!水只會在啟點與終點,以及所有的中繼點中提供,你必須選擇一個路徑,使得該路徑上所有相鄰兩個供水的地方之最大距離最小化才行,也就是路徑上所有相鄰的兩個點中之最遠的距離,使該段距離愈小愈好。在這個前題下,請選擇最短的路徑。

Input

輸入會有多組測試資料,每組測試資料的第一列會有三個整數r, c, k (3 <= r, c <= 20; 1 <= k <= 10)。接下來會有 r 列,每列有 c 個字元,表示島的地圖。波型符號 ~ 表示無法通過的海洋,井字符號 # 表示陸地,陸地會被海洋所圍繞。S表示啟點,T表示終點,啟點總是在岸邊。每一個中繼點以字母A~K唯一地表示,你必須最少拜訪過 k 個中繼點後到T點完成你的旅程,你可以重複地拜訪同一個中繼點,且拜訪的順序並不重要。

你只能在陸地上下左右行走每一步,也就是只能朝東南西北四個方向行走。陸地的高度都一樣,你無需考慮高低差的問題。你也可以假設所有中繼點都是可到達的,所以你只要照著要求選出一條最佳化的路徑就一定能獲得勝利。

測試資料如右圖所示。

Output

請列出每一組測試資料的最佳路徑,以E, W, S, N來表示東、西、南、北,如果有多組路徑可達到要求,請輸出字典順序最小的那組。

Sample Input

15 15 2
~~~~~~~~~~~~~~~
~~###~~~~~#~~~~
~##T###~#####~~
~~############~
~~###########~~
~~###########~~
~##B########~~~
~#########A##~~
~~###########~~
~~##########~~~
~##########~~~~
~~###~S#####~~~
~~~##~~####~~~~
~~~~~~~~##~~~~~
~~~~~~~~~~~~~~~

Sample Output

EEEENNNNNWWWWWWWNNNN

Explanation

上列中的最佳路徑以紅色字體表示如下(請勿做此輸出):
~~~~~~~~~~~~~~~
~~###~~~~~#~~~~
~##T###~#####~~
~~############~
~~###########~~
~~###########~~
~##B########~~~
~#########A##~~
~~###########~~
~~##########~~~
~##########~~~~
~~###~S#####~~~
~~~##~~####~~~~
~~~~~~~~##~~~~~
~~~~~~~~~~~~~~~

原文出處

沒有留言:

張貼留言