Avoid Knight Attack

题目描述

有一个由 $N^2$ 个格子组成的棋盘，具有 $N$ 行和 $N$ 列。 记 $(i,j)$ 为从顶部第 $i$ 行 $(1\leq i\leq N)$、从左侧第 $j$ 列 $(1\leq j\leq N)$ 的格子。 每个格子要么为空要么放有一枚棋子。 棋盘上放置了 $M$ 枚棋子，第 $k$ 枚 $(1\leq k\leq M)$ 棋子放在格子 $(a_k,b_k)$ 上。 你想把你的棋子放在一个空格子上，使得它不会被任何已存在的棋子吃掉。 放在格子 $(i,j)$ 的棋子可以吃到满足下列任一条件的格子上的棋子：

放在格子 $(i+2,j+1)$ 放在格子 $(i+1,j+2)$ 放在格子 $(i-1,j+2)$ 放在格子 $(i-2,j+1)$ 放在格子 $(i-2,j-1)$ 放在格子 $(i-1,j-2)$ 放在格子 $(i+1,j-2)$ 放在格子 $(i+2,j-1)$

这里，涉及不存在格子的条件被视为永远不成立。 例如，放在格子 $(4,4)$ 的棋子可以吃到下图中用蓝色所示格子上的棋子： 你可以把棋子放在多少个格子上？

输入格式

输入由标准输入按如下格式给出： $N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_M$ $b_M$

输出格式

输出可以放置你的棋子且不会被任何已存在棋子吃掉的空格子的数量。

8 6
1 4
2 1
3 8
4 5
5 2
8 3

38

1000000000 1
1 1

999999999999999997

20 10
1 4
7 11
7 15
8 10
11 6
12 5
13 1
15 2
20 10
20 15

338

提示

$1\leq N\leq10^9$ $1\leq M\leq2\times10^5$ $1\leq a_k\leq N,1\leq b_k\leq N\ (1\leq k\leq M)$ $(a_k,b_k)\neq(a_l,b_l)\ (1\leq k\lt l\leq M)$ 所有输入值均为整数。现有的棋子可以吃到下图中用蓝色所示的格子： 因此，你可以把棋子放在剩下的 $38$ 个格子上。
在 $10^{18}$ 个格子中，只有 $3$ 个格子不能使用：格子 $(1,1)$、$(2,3)$ 和 $(3,2)$。 注意答案可能为 $2^{32}$ 或更大。

标签: AtCoder|abc377C

来源

AtCoder|abc377C