欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

nyoj -1153.木叶村最安全的地方(思维)

程序员文章站 2022-03-24 10:45:36
...

题目描述

在火影忍者第200话积极且最强的救兵里面,纲手的得知30年前木叶村被埋藏了很多起爆符,玄翁想要利用30年前埋藏在木叶的起爆符来摧毁木叶。这是一件非常危险的事情,纲手立马安排人手排除这些起爆符,但是为了以防万一她决定想一个万全之策,我们把木叶村分解成一个n*m的矩阵,一共有n*m 个点。现在纲手知道每个起爆符的位置,并且每张起爆符都能炸掉它所在的行列和两个对角线的地方,现在有k张起爆符,并且给你每一张起爆符的位置(x,y)问木叶村一共有几个地方没有被攻击到,纲手会想办法吧所有的村民尽可能的往安全地带转移

nyoj -1153.木叶村最安全的地方(思维)

输入

第一行三个正整数 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;
}

 

相关标签: 思维