在输了一晚上的麻将之后,小 z 和小 c 卸掉了手机上的所有牌类游戏。不过这怎么可能阻挡得了他们上课颓废的决心呢?现在他们的目光盯在了棋类游戏上,但他们两个除了天天下飞行棋以外,几乎所有棋类游戏都只懂个大概规则。
“既然我们都会玩但只能玩一点点,不如我们自己搞个缝合怪出来吧!”
于是,在他们的精心脑洞之下,一个融合了围棋、象棋与军棋的奇妙游戏诞生了……
题目描述
游戏在一张长
棋子分为黑白两色,对局双方各执一方棋子。
每个棋子除了颜色以外还有等级,不妨设
轮到每方下棋时,他可以选择棋盘上的一个己方棋子沿网格线进行移动到另一个交叉点,称为走子。形式化定义走子的过程如下:选择一个坐标序列
- 对于任意
,坐标 和 之间必须有网格线直接相连,也就是说走子必须沿着网格线走; - 对于任意
,必须有 ,也就是说走子过程中不能经过重复位置,特别地 ,也就是说不能原地不动(或走回原地); - 对于任意
,坐标 上必须没有棋子,也就是说走子时不能越过已有的棋子; - 若
上没有棋子,称为普通走子,否则称为吃子。在吃子过程中,设正在走的棋子颜色为 ,等级为 ,被吃的棋子颜色为 ,等级为 ,则必须满足 ,换句话说只能吃与自己颜色不同,且等级不高于自己等级的棋子。
需要注意的是,由上述定义可以得出,不允许棋子在吃子后继续向前走。
网格线的状态含义如下所述:
- 如果
,代表此路不通,走子时不能经过这条网格线; - 如果
,代表这条网格线是一条“普通道路”,每次走子时棋子最多只能经过 条普通道路。 - 如果
,代表这条网格线是一条“直行道路”,每次走子时棋子可以经过任意条直行道路,但只能一直沿横向或一直沿纵向走,不能转弯。如沿直行道路从 经过 走到 是可以的,但是从 经过 走到 不行。 - 如果
,代表这条网格线是一条“互通道路”,每次走子时棋子可以经过任意条互通道路,且中途可任意转弯。
同时规定在一次走子过程中,棋子经过的网格线的状态必须全部相同,比如从
至于如何判断胜负等其它细节,与本题无关,故略去。
小 z 和小 c 开发出这款棋类游戏后,为了提升水平,想了一个训练的策略:一开始棋盘是空的,然后小 c 会每次往棋盘的某个空交叉点上放一枚棋子,小 z 需要快速计算出:若选择这枚新放上的棋子进行一次走子,棋盘上一共有多少个位置是能被走到的?注意:因为这只是思维训练,他们并不会真的走这枚棋子。
可怜的小 z 发现他的计算力不足以算出这个问题,只好向你求助。
输入格式
每个测试点由多组数据组成。
第一行:一个正整数
对于每组数据:
第一行:三个正整数
接下来
接下来
接下来
输出格式
对于每组数据输出
样例一
input
1 3 3 5 13 22 23 010 233 0 1 2 3 1 2 2 1 1 3 1 2 0 2 3 2 1 3 2 2
output
4 3 3 3 2
explanation
放置棋子
放置棋子
放置棋子
放置棋子
放置棋子
样例二
input
2 2 3 4 22 33 123 0 2 1 2 0 1 2 1 1 2 1 3 0 3 2 2 3 2 3 3 1 3 32 32 0 2 1 2 1 2 3 2 0 1 2 2
output
3 4 4 2 5 5 1
样例三、四
见附件下载。
数据范围
测试点编号 | 特殊性质 | ||
---|---|---|---|
无 | |||
无 | |||
不存在“直行道路”与“互通道路” | |||
不存在“互通道路” | |||
不存在“直行道路” | |||
无 |
对于
注:由于本题输入输出规模较大,建议使用较为快速的输入输出方式。
时间限制:
空间限制: