P2105 K皇后

小 Z 最近捡到了一个棋盘，他想在棋盘上摆放 K 个皇后。他想知道在他摆完这 K 个皇后之后，棋盘上还有多少个格子是不会被攻击到的。

注意：一个皇后会攻击到这个皇后所在的那一行，那一列，以及两条对角线。

输入格式

第一行三个正整数 n,m,K，表示棋盘的行列，以及小 Z 摆放的皇后的个数。

接下来 K 行，每行两个正整数 x,y，表示这个皇后被摆在了第 x行，第 y 列，数据保证任何两个皇后都不会被摆在同一个格子里。

输出格式

仅一个整数，表示棋盘上还有多少个格子是不会被攻击到的。

输入输出样例

输入 #1复制

12 13 6
10 4
12 10
1 1
2 3
3 2
2 6

输出 #1复制

25

说明/提示

• 对于 30\%30% 的数据，1\le n,m\le 5\times10^31≤n,m≤5×103，1\le K\le 5001≤K≤500；
• 对于另外 10\%10% 的数据，K=1K=1；
• 对于 100\%100% 的数据，1\le n,m\le 2\times 10^41≤n,m≤2×104，1\le K\le 5001≤K≤500。

 

我的思路是深搜,超时,看了网上代码,就是优化暴力,有个数学知识的点还没搞懂,代码以理解

超时代码 

#include <iostream>
using namespace std;
 
const int N=30000,M=30000;
 
struct node{
    int first,second;
}a[505];
int dx[8]={0,0,1,1,1,-1,-1,-1},dy[8]={1,-1,0,1,-1,0,1,-1};
int n,k,m,ans;
bool s[N][M];
 
void dfs(int x,int y,int kk){
    int xx=x+dx[kk],yy=y+dy[kk];
    if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
        s[xx][yy]= true;
        dfs(xx,yy,kk);
    }
    return;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++){
        scanf("%d%d",&a[i].first,&a[i].second);
        s[a[i].first][a[i].second]= true;
    }
    for(int i=1;i<=k;i++){
       for(int j=0;j<8;j++){
            int x=a[i].first+dx[j],y=a[i].second+dy[j];
            s[x][y]= true;
            dfs(x,y,j);
       }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) {
            printf("%d ",s[i][j]);
        }
        printf("\n");
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]==0){
                ans++;
            }
        }
    }
    printf("%d\n",ans);
}

 网上ac代码

#include<bits/stdc++.h>
using namespace std;
int x[501],y[501],n,m,k;
int flag[20001],vis[20001],sum,ans;
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++) cin>>x[i]>>y[i],vis[x[i]]=1;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]) continue;//当前行有国王直接跳过
        sum=m;
        for(int j=1;j<=k;j++)
        {
            if(flag[y[j]]!=i) sum--;//当前国王控制的列数
            flag[y[j]]=i;
            if(x[j]<i)//当前国王在当前行上方
            {
                if(y[j]+i-x[j]>=1&&y[j]+i-x[j]<=m)
                {//右下方向对角线
                    if(flag[y[j]+i-x[j]]!=i) sum--;
                    flag[y[j]+i-x[j]]=i;
                }
                if(y[j]-i+x[j]>=1&&y[j]-i+x[j]<=m)
                {//左下方向对角线
                    if(flag[y[j]-i+x[j]]!=i) sum--;
                    flag[y[j]-i+x[j]]=i;
                }
            }
            else //当前国王在当前行下方
            {
                if(y[j]+(x[j]-i)>=1&&y[j]+(x[j]-i)<=m)
                {//右下方向对角线
                    if(flag[y[j]+(x[j]-i)]!=i) sum--;
                    flag[y[j]+(x[j]-i)]=i;
                }
                if(y[j]-(x[j]-i)>=1&&y[j]-(x[j]-i)<=m)
                {//左下方向对角线
                    if(flag[y[j]-(x[j]-i)]!=i) sum--;
                    flag[y[j]-(x[j]-i)]=i;
                }
            }
        }
        ans+=sum;
    }
    cout<<ans;
}