m皇后（小白版）

m皇后（牛客） 题目链接

本题： https://ac.nowcoder.com/acm/problem/15295

“八皇后问题”题目链接： NOI： http://noi.openjudge.cn/ch0205/1700/ 洛谷： https://www.luogu.com.cn/problem/P1219

题目大意

棋盘上有若干皇后，每个皇后有八个方向，分别是上、下、左、右、左上、右上、左下、右下。存在其他皇后在此皇后的这八个方向，那么这个方向就是不安全的。 最后输出在0，1，2，3，4，5，6，7，8个方向上不安全的皇后的个数。

简单分析

1. 看到这种皇后八个方向的问题，我们第一时间会想到的就是“八皇后问题”。从“八皇后问题”中，我们学到的一种方法：与主对角线（包含主对角线）平行的直线上点的横纵坐标之差为定值；与副对角线（包含副对角线）平行的直线上点的横纵坐标之和为定值。因此，对于本题也可以试试是否可以运用这个方法。
2. 思考是否能暴力遍历？ 暴力1：遍历每个点，暴力它的八个方向，有点就记录，时间复杂度的极限大概是O(10^10)，显然不行。 暴力2：遍历每个点，再确定其他点是否在它的八个方向上，有点就记录，时间复杂度的极限大概也是O(10^10)，显然不行。 既然无法完全暴力，我们就要思考一下技巧了。
3. 我们尝试着从某个方向去遍历所有的点。 以确定某皇后左右是否安全为例：反映在图上，就是找此皇后的左边是否有皇后，右边是否有皇后。可以发现，此时，若此皇后左右存在不安全的其他皇后，那么这些皇后（包括此皇后）的横坐标都相同，不同的是纵坐标。再深度思考一下，也就是说，我们实际上比较的是与此皇后横坐标相同的皇后的纵坐标与此皇后的纵坐标的大小关系（这句话有点绕 ）。如果满足“横坐标与此皇后相同”的条件，且“其纵坐标小于此皇后的纵坐标”，那么就要标记此皇后的左侧是一个不安全的方向；如果满足“横坐标与此皇后相同”的条件，且“其纵坐标大于此皇后的纵坐标”，那么就要标记此皇后的右侧是一个不安全的方向。 进一步分析这个例子：如何高效的完成确定某皇后左右是否安全？这时我们要用到排序，按横坐标从小到大将所有皇后排序，横坐标相等的按纵坐标从小到大排序，从横坐标相等的里面比较纵坐标就行了。这样方便我们确定左右是否有其他皇后。（具体如何实现放在下一个标题下了）
4. “确定某皇后左右是否安全”的例子探索完了，该解决其他方向上的了。类比一下，要是“确定某皇后上下是否安全”，我们就找与此皇后纵坐标相同的其他皇后，比较横坐标大小，进行记录；要是“确定一三象限角平分线是否安全”，我们就找与此皇后横纵坐标之和相同的其他皇后，比较横坐标大小（比较纵坐标也可以，本质就是找相对位置的关系），进行记录；要是“确定二四象限角平分线是否安全”，我们就找与此皇后横纵坐标之差相同的其他皇后，比较横坐标大小（括号内容同上），进行记录。

实现讲解

1. 输入： 结构体输入，包括x，y，id。其中x表示横坐标，y表示纵坐标，id表示第id个皇后（就是为了给皇后编个号）
2. 核心代码实现： 建立四个cmp函数，用于分上述四种情况去sort。每次排完序之后，我们遍历每个顺序遍历每个点。以确定某皇后左右是否安全为例，如果此点左边的点的横坐标与此点的横坐标相同，那么此点左边的点的纵坐标一定比此点小，因为咱们就是这么排的序，所以满足“此点左边的点的横坐标与此点的横坐标相同”就让cnt[此点id]++，cnt[此点左边的点的id]++，表示此点左边不安全，记录一下；此点左边的点的右边不安全，记录一下。以此循环。思考一下，其实被遍历的每个点的cnt最多加两次，一次是遍历到自己时，另一次是遍历到它后面的一个点时。当遍历到自己时，cnt[自己]++表示加上我左边不安全的情况；当遍历到自己的下一个点的时候（即自己作为当前遍历点的左边的点时）cnt[自己，即当前遍历点的左边的点]++表示自己右边不安全的情况。 其他三个情况类似，不再赘述。
3. 输出 自己想办法输出cnt=0，1，2，3，4，5，6，7，8有几个就行了，很简单。

AC代码

#include
using namespace std;
const int N=100010;
int book[10],cnt[N];
struct queen{
 	int x,y,id;
}q[N];
bool cmp1(queen a,queen b){
	if(a.x==b.x) return a.y