如果能上 unordered_map
的话随便做,但是出题人卡了空间。
注意到 $1 \leq n,m \leq 2 \times 10^4$,$1 \leq k \leq 500$,而 $2 \times 10^4 \times 500 = 10^7$。
枚举行,枚举皇后,计算当前行有多少格子被皇后影响,开一个数组即可统计,注意清空数组时应该记录那些位置被使用,然后清空这些位置。
时间复杂度 $O(nk)$,空间复杂度 $O(n)$。
#include<bits/stdc++.h>
using namespace std;
struct Queen{int x,y;}a[505];
int n,m,k,ans,p[20005];
bool on[20005];
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++) scanf("%d%d",&a[i].x,&a[i].y);
for(int i=1;i<=n;i++){
int cnt=0,pos=0,fail=0;
for(int j=1;j<=k;j++) if(a[j].x==i) fail=1;
if(fail) continue;
for(int j=1;j<=k;j++){
if(!on[a[j].y]) p[++cnt]=a[j].y,on[a[j].y]=1;
pos=a[j].x+a[j].y-i;
if(pos>=1&&pos<=m&&!on[pos]) p[++cnt]=pos,on[pos]=1;
pos=a[j].y-a[j].x+i;
if(pos>=1&&pos<=m&&!on[pos]) p[++cnt]=pos,on[pos]=1;
}
for(int j=1;j<=cnt;j++) on[p[j]]=0;
ans+=m-cnt;
}
printf("%d\n",ans);
return 0;
}