2013年7月23日 星期二

1098 - Robots on Ice

這題的靈感來自於哈爾濱的冰雕節,在參賽隊伍回國前,北極大學(Arctic University) 的機器人將會帶領程式比賽的隊伍參觀這場慶典,他們打算從冬季結冰的湖水得到巨大的冰塊,為了監視脆弱的冰層,他們將湖畫分成網格狀,而讓機器人在湖面上運行檢查工作。

檢查工作中,將會有 3 個重要的 check-in 報到點,必須在此以無線電回報工作進度,而這三個點分別在路程的 1/4, 2/4, 3/4 的位置。為了避免與冰層表面不必要的摩擦,機器人打算從左下角 (0, 0) 出發,經過所有格子一次後,最後到 (0, 1)。如果有多種走法,而機器人盡可能每天使用不同路徑,而機器人一次只能移動四個方向一步(東西南北)。


寫一個程式,根據不同的網格大小,以及給定 3 個 check-in 點,計算有多少不同路徑種數。

例如:有一個網格 3 x 6,3 個 check-in 點順序位在 (2, 1) (2, 4) (0, 4),機器人一開始一定在 (0, 0) 出後,經過 18 個格子後,停在 (0, 1)。而會在第 4 ( = floor(18/4)) 步走到 (2, 1),第 9 ( = floor(2*18/4)) 步走到 (2, 4),第 13 ( = floor(3x18/4)) 步走到 (0, 4)。

如下圖表示將會只有兩種方式:



也許會存在沒有任何的合法路徑,如 4 x 3 網格,check-in 點分別在 (2,0), (3,2), (0,2)。

Input 

輸入有多組測資,每組第一行會有兩個整數  2 <= m, n <= 8,分別表示 行(row)與列(column)。而接下來會有 6 個整數 r1, c1, r2, c2r3, c3,
(0<= ri < m , 0 <= ci < n for i = 1, 2, 3)
最後一組 m = n = 0  結束程式。

Output 

對於每組測資,輸出測資組編號,以及其可能的路徑總數。

並且在指定步數時抵達報到點。

$$\left \lfloor i*m*n/4 \right \rfloor \text{for i = 1, 2,3 }$$

Sample Input 

3 6 
2 1 2 4 0 4 
4 3 
2 0 3 2 0 2 
0 0

Sample Output 

Case 1: 2 
Case 2: 0