题解 P2105 【K皇后】

gujialiang123 · 2019-09-16 18:18:57 · 题解

感觉我的可能是最简洁明了的了

简述一下思路

一行一行扫，如果当前行有国王直接跳过，否则遍历每个国王，每个国王对当前行有三个影响，一是对当前行和他列数相同的格子有攻击，二是他所占有的两条对角线可能会攻击到当前格子，这里要判断一下对角线延伸到当前行列数是否越界（在1-m中间），使用一个flag数组标记当前行每个位置是否被攻击到，每行遍历时开一个sum每次初始化为m，如果当前循环中已经没有被攻击过就sum--。

看到有人用memset每次清空flag，这里不需要，我们可以把flag定义为int类型，然后用当前行数作为标记，如果flag[i]不等于当前行数那就是没有攻击过，然后把这个位置的值赋成当前行的行数。

这样复杂度就是严格o(n*k),完全可以接受。

代码如下，比较短

#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;
 }