d733: 11329 - Curious Fleas
Tags :
Accepted rate : 22人/22人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-19 13:27

Content
你最珍貴的財產就是你的跳蚤馬戲團。主要的吸引力是這個馬戲團的六隻雜技跳蚤在表演。有一天你不小心打翻裝有這些跳蚤的容器,它們都佔據了整個 4x4的正方形瓷磚,充滿了您的廚房的地板。出乎意料的是,沒有兩隻相同的跳蚤在正方形瓷磚上。

 

你的兒子安迪有一個六個面正常的骰子,骰子每個面都和正方形瓷磚一樣大。你決定要玩一個遊戲。首先,您的骰子恰好在一個沒有跳蚤的瓷磚。然後你開始滾動骰子到邊緣任何一個的相鄰瓷磚。跳蚤們是非常好奇,他們喜歡探索。當您移動骰子到一個包含跳蚤的正方形瓷磚,跳蚤就會跳躍到骰子的底部。跳蚤是小到足夠隱藏在骰子上的點,所以他們在這個過程中並不會死。同樣地,如果跳蚤所在的那一面翻轉到地板上時,它就會跳躍到正方形瓷磚上。

 
你的遊戲的目標是將翻轉骰子到所有的跳蚤都在骰子上時,就算是結束。骰子不能離開你的廚房當中的4x4格子。以下的圖片是一個範例同時也是第一筆測資:

 

第一行顯示的數字表示接下來有幾筆的測試資料。每個測試資料包括一個空行和四行且每行皆有四個字元描述著初始盤面。'.'表示空格、'X'表示一隻跳蚤、'D'表示骰子的初始位置。而且每一筆測試資料都一定會有一個骰子和六隻跳蚤。
 

 對於每個測試資料,輸出一行包含一個數字為最少翻轉的次數,必須在同一時間點每一個面都要有一隻跳蚤才算結束。如果測試資料無法解決,輸出"impossible"。

Input
Output
Sample Input
2

...X
XXXX
D..X
....

DX.X
.X..
..X.
X..X
Sample Output
8
14
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <1M
Hint :

 如果UVA想衝排名這題是很不錯的選擇~~只要有1秒就可以進了!

譯:asas

Tags:
出處:
UVa11329 [管理者:
asas (向諸神與地雷醬獻上祈禱)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」