自动搬运

查看原文

来自洛谷，原作者为

	gujialiang123 **

搬运于2025-08-24 21:34:02，当前版本为作者最后更新于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;
 }