盲区（blindspot）

题目描述

在一个 n 行 m 列的网格上，行从上到下编号为 1 到 n，列从左到右编号为 1 到 m，第 r 行第 c 列的单元记为 (r, c)。

网格中可能放置三种站点：

• 定向发射站：向横、竖、两条对角线共 8 个方向发射信号。信号沿直线传播，遇到任何站点就停止；被信号穿过的空单元视为被覆盖。发射站所在单元本身不算被覆盖（它已被站点占用）。
• 跳跃干扰站：干扰到与它相距一个 2 × 3 或 3 × 2 矩形对角位置的单元，即行列差绝对值一项为 1、另一项为 2 的单元，因此一个跳跃干扰站最多有 8 个落点。这些落点视为被覆盖，中间经过的单元不受影响。
• 阻挡站：只占据一个单元，自身不产生任何覆盖。

如果一个空单元既没有被站点占用，也没有被任何信号或干扰覆盖，就称它为盲区单元（safe square）。

给定网格中所有站点的位置，请你计算盲区单元的数量。

输入格式

输入包含多组测试数据，测试数据组数不超过 20。

每组测试数据的第一行为两个整数 n, m，表示网格的行数和列数。

接下来有三行，分别描述三类站点，每行的格式为：

k r1 c1 r2 c2 ... rk ck

其中 k 表示该类站点的数量，后面跟着 2k 个整数表示站点坐标；当 k = 0 时，该行只有一个整数 0。

三行依次为：定向发射站、跳跃干扰站、阻挡站。

输入以一行 0 0 结束，该行之后没有站点信息，也不产生输出。

输出格式

对于每个测试用例输出一行。设第 b 个测试用例的盲区单元数量为 s，输出：

Board b has s safe squares.

其中 b 从 1 开始递增。

样例输入

4 4
2 1 4 2 4
1 1 2
1 2 3
2 3
1 1 2
1 1 1
0
1000 1000
1 3 3
0
0
0 0

样例输出

Board 1 has 6 safe squares.
Board 2 has 0 safe squares.
Board 3 has 996998 safe squares.

样例解释

第一个测试用例为 4 × 4 的网格：

• 定向发射站位于 (1, 4)、(2, 4)；
• 跳跃干扰站位于 (1, 2)；
• 阻挡站位于 (2, 3)。

被覆盖的单元为 (1, 3)、(3, 4)、(4, 4)、(3, 3)、(4, 2)、(3, 1)，因此盲区单元为 (1, 1)、(2, 1)、(2, 2)、(3, 2)、(4, 1)、(4, 3)，共 6 个。

第二个测试用例为 2 × 3 的网格，定向发射站位于 (1, 2)、跳跃干扰站位于 (1, 1)，所有空单元都被覆盖，因此盲区单元数量为 0。

第三个测试用例为 1000 × 1000 的网格，只有一个定向发射站位于 (3, 3)。横向覆盖 999 个单元，纵向覆盖 999 个单元，两条对角线分别覆盖 999 和 4 个单元，共覆盖 3001 个单元，因此盲区单元数量为 1000000 - 1 - 3001 = 996998。

数据范围与约定

对于所有测试数据：

• 1 ≤ n, m ≤ 1000
• 0 ≤ d, j, z ≤ 100，其中 d, j, z 分别是定向发射站、跳跃干扰站、阻挡站的数量
• 所有站点坐标满足 1 ≤ r ≤ n，1 ≤ c ≤ m，且站点位置两两不同
• 测试数据组数不超过 20

• 特殊性质 A：每个测试用例都有 d = 0，即没有定向发射站。
• 特殊性质 B：每个测试用例都有 d = 1 且 j = z = 0，即只有一个定向发射站，且没有其他站点。

时间限制：1.0 秒　空间限制：512 MiB