2013年7月6日 星期六

10716 - Evil Straw Warts Live

Problem D: Evil Straw Warts Live

一個回文字符串被定義為等同於自己本身的反轉。

給定一個字串,其不一定是個回文 ,計算最少的 swap (交換次數) 使這個字串成為回文。
swap 操作定義為交換兩個相鄰字符。

例如字串 "mamad" 可以使用三次 swaps 轉換成回文字串 "madam":

  • swap "ad" 後的結果為 "mamda"
  • swap "md" 後的結果為 "madma"
  • swap "ma" 後的結果為 "madam" 
測資第一行有一個整數 n 表示接下來的測資組數。
對於每組字串,長度最多為 100 的小寫字母夠成,輸出最少的交換次數,
如果沒辦法轉換成回文字串,則輸出  "Impossible"。

Sample Input

3
mamad
asflkj
aabb

Output for Sample Input

3
Impossible
2

Gordon V. Cormack