最近和同學在準備一個元旦晚會的節目，wonder girls 的一段mv舞蹈：tell me。 胡思亂想中想到一個很有意思的小問題，設計的好的話其實可以作為比賽中前菜。。用來熱身。。不算很水。。但是也不難。。有幾個小tricks還是要稍微注意下，下面簡單的描述一下。
現在有五位同學在練習舞蹈，五位同學有一定的隊形，在舞蹈中需要時常變換隊形，那么請問從當前隊形變換成指定隊形至少需要做多少次隊形轉換。我們規定五位同學一次隊形轉換定義如下:
1.五位同學中必須至少有一位同學移動，且只能移動一步。
2.移動的位置必須為空或者即將為空，即將為空的意思是兩個同步移動。
3.移動的方向是周圍的8個方向。
比如如下圖所示：（左邊為當前位置，右邊是目標位置）
可以知道只需要一次轉化即可轉為目標位置，如下圖：
下面作出其他題目假設，題目輸入每次都給出兩個五行五列的矩陣，0表示該位置有人，1表示該位置沒有人，要求移動時不能超出這個5*5的矩陣（這個約束是為了簡化計算，如果不限定這個約束題目好像會更開放一些，還沒想清楚如果不約束怎么搞）,
比如上圖可以給出如下輸入：
0 0 0 0 0 1 1 1 0 0
0 1 0 0 0 1 1 0 0 0
1 1 1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
輸出答案：1
ps： 要注意要求的圖形是形狀相同即可。。并不要求在矩陣中的相對位置也必須相同。
posted on 2009-11-02 21:39
zoyi 閱讀(429)
評論(0) 編輯 收藏 引用 所屬分類:
acm