冬天來臨,天氣越來越冷,許多動物採取不同的方法來適應冬天。
- 遷徙,移動到溫暖的地方。
- 很少有動物仍在冬天保持活躍。
- 冬眠,動物藉由深沉睡眠,降低體溫、心跳速度,而在秋天時準備足夠的食物以及體內脂肪。
而這題著重於第三點的例子,觀察一種特別的熊。
這種熊在一個特別的森林,將這個森林定義為 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 |
沒有留言:
張貼留言