2013年9月18日 星期三

11487 - Gathering Food

冬天來臨,天氣越來越冷,許多動物採取不同的方法來適應冬天。

- 遷徙,移動到溫暖的地方。
- 很少有動物仍在冬天保持活躍。
- 冬眠,動物藉由深沉睡眠,降低體溫、心跳速度,而在秋天時準備足夠的食物以及體內脂肪。


而這題著重於第三點的例子,觀察一種特別的熊。


這種熊在一個特別的森林,將這個森林定義為 N x N 的網狀格子,每個格子只會有下列三種資訊。


'.' 空地
'#' 障礙物
[A-Z] 英文字母

森林中至少存在一個英文字母,所有字母只會存在唯一一個,如果存在有 n 個字母,這必然只會存在前 n 個字母,即當 n = 3 時,確切只會有 1 A, 1 B, 1 C

這些字母表示當地區的食物,熊會從 'A' 開始搜集其他食物,每次只會往四個方向(上下左右)移動,由於特別的習性,會根據字母順序搜集食物,當熊到達食物所在地時,才能將食物收集起來。


計算熊收集食物的最少移動步數,以及在最少移動步數下,有多少移動方法。


// 翻譯備註,非要撿起的食物必須當做障礙物。
Input

有多組測資,每組第一行有一個整數 N (N <= 10)。

Output

對於每組測資,輸出測資組編號,如果無法搜集到所有食物,則輸出 ‘Impossible’。

反之分別輸出最短路徑長及路徑個數,輸出 mod 20437 後的結果即可。

Sample Input                             Output for Sample Input

5
A....
####.
..B..
.####
C.DE.
2
A.
.B
2
A#
#B

0
Case 1: 15 1
Case 2: 2 2
Case 3: Impossible