nyoj -1153.木叶村最安全的地方(思维)
程序员文章站
2022-03-24 10:45:36
...
题目描述
在火影忍者第200话积极且最强的救兵里面,纲手的得知30年前木叶村被埋藏了很多起爆符,玄翁想要利用30年前埋藏在木叶的起爆符来摧毁木叶。这是一件非常危险的事情,纲手立马安排人手排除这些起爆符,但是为了以防万一她决定想一个万全之策,我们把木叶村分解成一个n*m的矩阵,一共有n*m 个点。现在纲手知道每个起爆符的位置,并且每张起爆符都能炸掉它所在的行列和两个对角线的地方,现在有k张起爆符,并且给你每一张起爆符的位置(x,y)问木叶村一共有几个地方没有被攻击到,纲手会想办法吧所有的村民尽可能的往安全地带转移
输入
第一行三个正整数 n,m,K,表示木叶村的大小,k张起爆符 (n, m<=10000, k<=500)
接下来K行,每行两个正整数x,y,表示这个起爆符被摆在了第x行,第y列,数据保证没有任何两个=起爆符会被摆在同一个格子里。
输出
一个数表示木叶村一共有几个安全的地方
样例输入
12 13 6
10 4
12 10
1 1
2 3
3 2
2 6
样例输出
25
提示
第一个样例如图片所示 紫色的点代表安全地带
思路:比赛的时候没做出来,以往该类问题直接上表模拟,但这道题卡时间过不了,模拟最后会遍历一下全图就已经是10^8,超过1s的限制,所以需要换一种方法。标记是肯定要标记的,考虑如何标记来优化时间。可以以行或列为标准,例如以行为标准,输入时标记,输入结束后遍历幸存的行,先标记已知点所在的列,再根据其他行列标记实现对角线的标记,再将每行幸存的点累加。
代码如下:
#include<set>
#include<map>
#include<list>
#include<deque>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<stdlib.h>
#include<string.h>
//#include<ext/rope>
#include<iostream>
#include<algorithm>
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define per(i,a,b) for(int i=a;i<=b;++i)
#define rep(i,a,b) for(int i=a;i>=b;--i)
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
#define LL long long
#define swap(a,b) {int t=a;a=b;b=t}
using namespace std;
//using namespace __gnu_cxx;
#define maxn 60000+1000
int a[maxn],vis[maxn],b[maxn],fa[maxn];//vis是行标记,fa是列标记
int main()
{
int n,m,k;
cin>>n>>m>>k;
memset(vis,0,sizeof(vis));
for(int j=0;j<k;j++)
{
cin>>a[j]>>b[j];
vis[a[j]]=1;//有雷的 行(被废)
}
int ans=0;
for(int j=1;j<=n;j++)//枚举每行
{
if(vis[j]==0)//幸存的行
{
int sum=m;//总列数
memset(fa,0,sizeof(fa));
for(int i=0;i<k;i++)
{
if(fa[b[i]]==0)//有雷的 列(废)
{
fa[b[i]]=1;//标记
sum--;//减少
}
int x=abs(j-a[i])+b[i],y=b[i]-abs(j-a[i]);//根据上一行的情况来判断该行
if(x>=1&&x<=m&&fa[x]==0)//对角线有 雷
{
fa[x]=1;
sum--;
}
if(y>=1&&y<=m&&fa[y]==0)
{
fa[y]=1;
sum--;
}
}
ans+=sum;//幸存点累加
}
}
cout<<ans<<endl;
return 0;
}