\(\color{Red}{描述}\)
\(在n*n的棋盘上有m个K皇后，每个皇后可能被来自8个方向的其他皇后攻击\)
\(每个皇后只可能被(0-8)只皇后攻击，分别求出被(0-8)只皇后攻击的皇后数量\)
\(对于一个皇后来说，怎么找到上下左右对角线是否有皇后才是关键\)
\(如果把皇后按照x坐标分类装进vector中,对y排序\)
\(对于相同x坐标一组的皇后来说,如果是这组的第一个或最后一个,那么它只能收到左边或右边的皇后攻击。(因为按照y排序过)\)
\(如果处于中间的皇后，可以收到左右两个皇后攻击。\)
\(\color{Purple}{然后类似的我们按照y坐标分类,左对角线分类，有对角线分类。}\)
\(左对角线的x-y是固定的，右对角线的x+y是固定的，按照这个作为分类依据。\)
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+1;
int n,m,ans[maxn],isok[10];
vector<int>vec[maxn*3];
struct p{
int x,y,id;
}a[maxn];
void init(){
for(int i=0;i<maxn*3;i++) vec[i].clear();
}
void print(){
for(int i=1;i<=m;i++) cout<<ans[i]<<" ";
cout<<endl;
}
bool coy(p a,p b){return a.y<b.y;}
bool cox(p a,p b){return a.x<b.x;}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i].x>>a[i].y;
a[i].id=i;
}
//处理列
sort(a+1,a+1+m,coy);
for(int i=1;i<=m;i++)
vec[a[i].x].push_back(a[i].id);
for(int i=1;i<=n;i++)
{
if(vec[i].size()<=1) continue;
for(int j=0;j<vec[i].size();j++)
if(j==0||j==vec[i].size()-1) ans[vec[i][j]]++;
else ans[vec[i][j]]+=2;
}
init();
sort(a+1,a+1+m,cox);
for(int i=1;i<=m;i++)
vec[a[i].y].push_back(a[i].id);
for(int i=1;i<=n;i++)
{
if(vec[i].size()<=1) continue;
for(int j=0;j<vec[i].size();j++)
if(j==0||j==vec[i].size()-1) ans[vec[i][j]]++;
else ans[vec[i][j]]+=2;
}
init();
//右对角的x+y都相同
for(int i=1;i<=m;i++)//上面已经按照x排序了
vec[a[i].x+a[i].y].push_back(a[i].id);
for(int i=1;i<=2*n;i++)
{
if(vec[i].size()<=1) continue;
for(int j=0;j<vec[i].size();j++)
if(j==0||j==vec[i].size()-1) ans[vec[i][j]]++;
else ans[vec[i][j]]+=2;
}
init();
//左对角的x-y都相同
for(int i=1;i<=m;i++)
vec[int(a[i].x-a[i].y+1e5)].push_back(a[i].id);
for(int i=0;i<=2e5;i++)
{
if(vec[i].size()<=1) continue;
for(int j=0;j<vec[i].size();j++)
if(j==0||j==vec[i].size()-1) ans[vec[i][j]]++;
else ans[vec[i][j]]+=2;
}
for(int i=1;i<=m;i++) isok[ans[i]]++;
for(int i=0;i<=8;i++) cout<<isok[i]<<" ";
}
E. Yet Another Task with Queens（分类思想）
原文：https://www.cnblogs.com/iss-ue/p/12829822.html