题目详情
返回题库题目描述
有一个由$N^2$个正方形组成的网格，网格中有N行和N列。(i,j)表示从上往下(1≤i≤N)的第i行和从左往上(1≤j≤N)的第j列的正方形。
每个方格要么是空的，要么放了一颗棋子。网格上有M个棋子，而k-(1≤k≤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，N代表方格矩阵大小，M代表矩阵上棋子的数量
接下来M行，每行一个a和b代表棋子在棋盘上的位置
数据范围：
- 1≤N≤$10^9$
- 1≤M≤2×$10^5$
- 1≤$a_k$≤N,1≤$b_k$≤N(1≤k≤M)
输出描述
输出一个数：在不被现有棋子吃掉的情况下可以放置棋子的空方格数
提示
样例1：
现有棋子可以吃掉下图中蓝色方格中的棋子：
所以答案是38