2009年7月20日 星期一

ICPC 2563 Picture Puzzle



給定九個版塊,每一塊對應四邊的字母的導向(左或右),可以透過旋轉及隨意擺於位置,構造出可行還原情況。可行的意思指若兩個版塊相鄰,它們必須對應相字的字母且導向不相同。除了中間的那塊不可旋轉。求任意可行解。

基本上與數獨解差不多,甚至乎比它要簡單。每次放置版塊的時候要記下它是哪一塊,還有旋轉了多少遍(最多3遍)。假設放置次序依上至下、左至右的順序,則只在放置後檢查左及上方的版塊即成。

撇除輸出格式,本題也是簡單窮舉練習題。

沒有留言: