#7607. 【提高】跳马 普及−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

投完篮后小 X 浑身酸爽,心情愉快地备课去了,第一次上课首先要教小朋友们各种棋子的走法,并且要设计练习帮助小朋友们巩固记忆,小 X 发现马的跳法将是第一节课的难点,首先马的走法很不规则, 它是先沿着直线走一格,然后再沿着斜线走一格,也就是俗称的“马走日”,但中国像棋与国际象棋有所不同,首先中国象棋是从一个交叉点上移动到另一个交叉点上,而国际象棋棋子则在方格中移动; 其次,中国象棋的马还有“蹩马脚”的规则,即如果在马前行的道路上有一个棋子(该棋子可以是任意一方的)则称马被蹩住脚了,它就跳不到相应的位置上,这个蹩字读“别”,意思为“绊”。下图为马的走法规则:

“马走日”的行棋有条规定:马先沿直线走一格,然后再沿斜线走一格。马每次跳一个“日”字,就是从“日”字的一个角走到其对角,不管这个“日”字是立着还是横着,只要没有被蹩住脚,它都可以跳过去。

如图 1 所示,当马在棋盘中部的时候,如果没有障碍,最多能够看管住 8 个点,所以人们夸它是“八面威风”。如果跳到边线上,它的威力就小多了,如图 2 所示,我们看到红马在边线上,最多可以看管住 4 个点,减少了一半的管辖范围。如果跳到角上, 则威力再减半!但是马有一个最大的弱点——害怕被“蹩马脚”,也叫“绊马脚”。一旦马脚被蹩,就寸步难行。怎样是“蹩马脚” 呢?如果紧邻马行进方向的交叉点上有一个棋子(可以是任何一方棋子),马就不能跳过去,这就是“蹩马脚” 。如下图中所示:

如果在交叉点 A 处有一枚棋子,则图中的马就跳不到 1 和 2 两个交叉点上了;同理如果在交叉点 B 处有一枚棋子,则图中的马就跳不到 3 和 4 两个交叉点上了,如果在交叉点 C 处有一枚棋子,则图中的马就跳不到 5 和 6 两个交叉点上了,如果在交叉点 D 处有一枚棋子,则图中的马就跳不到 7 和 8 两个交叉点上了。

现在小 X 给你一个棋盘上的局面,此局面最多会有两个马,并且如果有两个马则它们一定是同一方的,另外还有许多别的棋子分布在棋盘上,这些棋子可能是己方的,也可能是对方的,小 X 要你指出有多少个对方的棋子会被马吃到,只要是在马一步能跳到的位置上有一个对方的棋子,则马就能吃到这个棋子。在象棋规则中任何时候任何棋子都不能吃己方的棋子!

输入格式

输入数据第一行为一个正整数 n, n=1 或 2,表示棋盘上有 n 个马,这 n 个马属于同一方。接下来 n 行每行包含两个整数表示马的位置,如果有两个马,则它们的位置保证不相同。

接下来的第 n+2 行为一个整数 m,表示棋盘上有 m 个棋子,最后 m 行每行有 3 个整数,表示一个棋子的信息,前两个数为棋子的位置,第三个数表示该棋子与马的关系, 0 表示它与马是同一方的,可以蹩马脚,但不可以被马吃; 1 表示它与马不是同一方的,既可以蹩马脚,又可以被马吃。棋盘上的位置是这样表示的,我们把棋盘上的每条竖线从左往右用 0~8 编号,把棋盘上的每条横线从下往上用 0~9 编号,上图已将编号标在棋盘的下边和左边,图中的马的位置就是(4,6), ①号点的位置就是(3,8)。

输出格式

输出数据仅有一行包含一个整数,表示马能够吃到的对方棋子的数量。 如果一个棋子同时被两个马吃到,这个棋子只能被统计一次!

样例

样例输入1

1
4 6
5
3 8 1
4 7 1
5 8 1
6 7 0
6 5 1

样例输出1

1

数据范围与提示

【样例解释】
这匹马只能吃到(6,5)位置上的棋子。 (3,8)和(5,8)被(4,7)蹩马脚了, (6,7)则是自己一方的棋子。

【数据范围】
70%的数据棋盘上只有一个马,且其中 30%的数据不存在“蹩马脚” 的情况。
100%的数据棋盘上最多只有两个马,同一位置保证只有一个棋子,并且位置不会超出棋盘的范围。