非常简单的一道暴力
看到n和m都是(10^4)级别就应该想到了
开始的想法是开个bool类型的n*m的数组,根据K个皇后用筛法筛掉被攻击的格子,筛掉一个ans--
其实不用这样。枚举每一行,枚举皇后,只开m容量的标记数组。
把这一行的格子筛去统计答案,这样空间也不会爆。也就是第一次筛去某个格子就ans--。筛完一行就清空标记数组。
其实不必这样。我们可以开int类型的数组,每次不标记成1,标记成当前的行数,这样可以不清空也不会影响判断。
#include <bits/stdc++.h>
using namespace std;
int n,m,k,a[509],b[509];
bool x[20009],y[20009],flag[200009];
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=k;i++)
{
cin>>a[i]>>b[i];
x[a[i]]=y[b[i]]=1;//也许没有什么用??
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(x[i]) continue;
int p=m;
for(int j=1;j<=k;j++)
{
if(flag[b[j]]==0) flag[b[j]]=1,p--;
int z=b[j]-a[j]+i;
if(z>=1&&z<=m&&flag[z]==0) flag[z]=1,p--;
z=2*b[j]-z;
if(z>=1&&z<=m&&flag[z]==0) flag[z]=1,p--;
}
ans+=p;
memset(flag,0,sizeof(flag));//可以开int的
}
cout<<ans;
}