#Pusaco12janbronze3. 放牧

放牧

放牧

题目描述

由于预算有限,农夫约翰J开始缩小他的农场规模,现在只有5米5米的正方形这么大了!由5×5个1米×1米的正方形格子组成,(1,1)在左上角,(5,5)在右下角: (1,1) (1,2) (1,3) (1,4) (1,5) (2,1) (2,2) (2,3) (2,4) (2,5) (3,1) (3,2) (3,3) (3,4) (3,5) (4,1) (4,2) (4,3) (4,4) (4,5) (5,1) (5,2) (5,3) (5,4) (5,5)

除了K(0 <= K <= 22, K 是偶数)个贫瘠的方格外的其它小正方形格子都长满了草,一开始一只名叫贝茜的奶牛在(1,1)格子的位置,这里一定会有草,名叫米尔德里斯的奶牛在(5,5)这个格子,这个位置也一定会有草。每过半小时,贝茜和米尔德里斯会吃光她们各自所在格子的草然后一起移向相依的一个有草的格子(东,西,南,北)。她们想吃光所有格子的草最后精确地在同一个位置结束。请计算能达成这种状态的所有路线数。贝茜和米尔德里斯总是向长有草的格子移动,她们不会移向同一个格子,除非那是仅剩的最后一个格子。

输入格式

第1行:整数K。第2..1+K行:每行包含一个没有长草的格子位置(i,j)。

输出格式

第1行:贝茜和米尔德里斯能够吃光所有草且最后停留在相同位置的所有走法数。

数据范围

(原站未提供,导入后需人工补齐)

样例

4
3 2
3 3
3 4
3 1
1

提示

输入描述:初始的格子如下所示(这里的.表示长满草的格子,x表示没有草的格子,b表示贝茜的出发点,m表示米尔德里斯的出发点):

![1.gif](file://534a8cbb1c.gif)

输出描述:这里只有1种可能的解决方案,最后贝茜和米尔德里斯相遇在(3,5)这个格子:

![2.gif](file://bd78512efa.gif)