SP1706 QKP - Queens, Knights and Pawns
题目描述
相信大家都已经很熟悉著名的「8 皇后问题」了，该问题要求将 8 个皇后放在一个棋盘上，使得它们互不攻击。在这道题目中，你会得到一些皇后、骑士和兵的初始位置，你需要找到棋盘上没有被皇后或骑士攻击到的格子数量，我们称这些格子为「安全格」。这里，兵只能用来阻挡，并没有攻击能力。下图展示的棋盘共有 6 个安全格子（阴影部分即为安全格）。
回顾一下规则，骑士可以跳到以自身为中心的 2x3 矩形的对角线位置；皇后可以朝任何水平方向、垂直方向或对角线前进，但直到遇到阻挡者。请注意，骑士的行进不会被其他棋子阻挡。
输入格式
输入包含多组测试用例。每组测试数据由 4 行组成：
第一行包含两个整数 $n$ 和 $m$，分别表示棋盘的行数和列数，取值不超过 1000。
接下来的三行以以下格式给出，分别表示皇后、骑士和兵的位置：
_k r$_{1} c$_{1} r$_{2} c$_{2} · · · r$_{k} c$_{k}_
其中，$k$ 为当前棋子的数量，$r_i$ 和 $c_i$ 分别表示第 $i$ 个棋子所在的行和列，行和列的编号从 1 开始。每种棋子的数量不超过 100。当 $n = m = 0$ 时，表示输入结束。
输出格式
对于每组测试数据，输出格式如下：
**_Board b has s safe squares._**
其中，_b_ 是棋盘的编号（从 1 开始），_s_ 是安全格子的数量。
**本翻译由 AI 自动生成**