思路

暴力 $O(n^3)$ 不可取.我们先扫描一遍棋盘。用 $r,c$ 数组来统计第i行/第i列有多少个监视哨。对于处于同一正副对角线的两点，有如下规律:

正对角线：两点的横纵坐标之差x-y相等.所以用x-y来对正对角线编号

副对角线：两点的横纵坐标之和相等.所以用x+y来对正对角线编号

所以再使用 $x,y$ 数组来记录第i个正负对角线的监视哨个数。

题目内容

在一个 $n \times n$ 的方格矩阵中，需要布置监视哨。每个监视哨能监视其所在行、所在列以及两条对角线（ $45^\circ$ 和 $135^\circ$ 方向）上的所有位置。如果两个监视哨位于同一行、同一列或同一条对角线上，它们就会相互干扰。

现在，矩阵中已经预先放置了一些监视哨，且保证这些已有的哨站之间不存在干扰。你需要再选择一个尚未放置哨站的方格，放入一个新的监视哨，使得加入后所有哨站仍然互不干扰。请求出满足要求的空位个数。

网格边长 $n$ 不超过 1000。保证输入的已放置哨站之间互不干扰。

第一行包含一个整数 $n$ ，表示矩阵的边长。