回分類題庫
h060: D.賽車
關鍵字: NPSC 2009 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 17 Times / 13 Users | Submit : 44 Times / 14 Users | Accepted rate : 93%
題目加入時間 : 2012-11-04 02:08

Content: 简体中文

因為近年來油價不斷攀升,一年一度在阿里不達國舉辦的阿里不達賽車大賽終於在今年有了新的規則。從今年開始,賽車改為三台車一隊,所有隊伍的每台車都必須用一樣的速度前進。三台車加起來使用的燃油最少的隊伍將獲得冠軍。

身為主辦國參賽隊伍榮譽教練的阿里不達國王為了要贏得冠軍,早就請來許多科學家實驗如何省油,他們發現油耗完全取決於賽車變換車道的次數以及跑道的長度(比賽規定賽車永遠只能往正前方、左前方、右前方前進)。

下圖是一個 7×4 的跑道,黑色表示路面太崎嶇賽車沒辦法行駛的地方(因為國王去年一時興起要在全國每個路口都蓋公廁,所以阿里不達國現在沒有錢修賽道)。比賽起點在最右邊,如果賽車走淺灰色的路徑(長度 7 ),油耗就是 7。如果走斜線標示的路徑(長度 7 + 變換車道 1 次),油耗就是 7+1=8。

給定賽道和三台車出發的位置,你的任務是要算出最少必須消耗的油量。

Input:

第一行只有一個數字 T (T<=100),表示測資的數量。第二行開始為測資。
每筆測資的第一行有兩個數字 R 和 C ( R<=10, C<=50 ),表示賽道的高與寬。接下來的 R 行分別包含 C 個字元,表示賽道的地圖。各字元表示意義如下:
# 障礙
C 賽車起始位置(共三個,一定在賽道最右邊)
. 可以行駛的位置

Output:

對每一筆測資輸出最小油耗,若無解則輸出Impossible,每筆測資後換行。注意賽車行進途中路徑不可重疊。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
3 4
...C
...C
...C
4 7
......C
..##..C
....#..
......C
4 5
..##C
....C
..#..
..#.C

Sample Output :

12
22
Impossible

Hint :

Author :

NPSC 2009 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum