2011年10月29日 星期六

208 - Firetruck

Center City的消防局與交通部合作,同步更新市區街道的運作情形,因為任何一天都可能因為道路維護或整修的需要而封閉部份道路,消防車需要選擇適當的路徑抵達火場,避免誤入已封閉的路段而延誤救援。

城市已被區分為不重疊的行政區,每一區都有一個消防局,當有火災警報時,火災地點所在行政區的消防局會被通報,並指示通往火災現場的所有可能的路徑。本題請你寫一個程式找出所有可能的路徑。

Input

每一個行政區的地圖都是獨立的,所有地點的編號皆為小於21的正整數,且消防局所在的地點一定是#1,每組測試資料會提供火災地點及路線圖,詳細說明如下:
  • 每組測試資料的第一列有一個整數,表示火災地點的編號。
  • 接下來每一列會有兩個以一到多個空白字元隔開的正整數,表示這兩個地點之間的聯絡道路是正常運作的(例如:4 7 表示4與7之間的道路是可行走的)
  • 最後以兩個0表示測試資料結束。

Output

請對每組測試資料輸出其資料編號(CASE #1, CASE #2...),並分別在不同列輸出每一條可行的路徑,並依序輸出路徑所經過的地點,且同一個地點不能重複經過兩次。最後一列請輸出所有路徑總數,請參考範列資料。

Sample Input

6
1 2
1 3
3 4
3 5
4 6
5 6
2 3
2 4
0 0
4
2 3
3 4
5 1
1 6
7 8
8 9
2 5
5 7
3 1
1 8
4 6
6 9
0 0

Sample Output

CASE 1:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
There are 7 routes from the firestation to streetcorner 6.
CASE 2:
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
There are 8 routes from the firestation to streetcorner 4.

原文出處

沒有留言:

張貼留言