1883: 放牧

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:4 通过:2

题目描述

由于最近的预算削减,FJ 缩小了他的农场,因此他的奶牛的放牧区只有 5 x 5 的场地! 
其中 (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 个格子没有草。 
奶牛 Bessie 在方格 (1,1) 开始吃草,该方格总是长满草。
奶牛 Mildred 开始在方格 (5,5) 吃草,该方格也总是长满草。
每半小时,Bessie 和 Mildred 吃完各自方格中的所有草,然后各自移动到相邻的长满草的方格(上、下、左、右)。 
他们想吃掉所有长满草的方块,并最终到达完全相同的最终位置。 
请计算这可能发生的不同方式的数量。 
Bessie 和 Mildred 总是移动到长满草的方格上,而且他们永远不会同时移动到同一个方格上,除非那是最后一个剩下的长满草的方格。

输入格式

输入第一行为正整数 K 。(0 <= K <= 22,K为偶数
接下来 K 行,每行为两个整数 x 和 y ,表示对应不长草格子的坐标。

输入样例 复制

4
3 2
3 3
3 4
3 1

输出样例 复制

1

数据范围与提示

下图为样例唯一的方案。其中x表示不长草的格子。b和m分别表示两头牛。

b  b--b  b--b
|  |  |  |  |
b--b  b--b  b
            |
x  x  x  x b/m
            |
m--m--m--m--m
|
m--m--m--m--m
来源:USACO 2012.1