正文

洛谷——p2074危险区域

author  author  2022-09-20  463

关键词：

P2074 危险区域

题目背景

一个恐怖组织在一座城市中安放了定时炸弹，其威力巨大，现在这里的警长想知道最坏的情况下会有多少街区受威胁。

题目描述

在一个城市有N*M个街区，每个街区由坐标描述，如图所示：

行列 1 2 3 … M

1 (1,1) (1,2) (1,3) … (1,M)

2 (2,1) (2,2) (2,3) … (2,M)

3 (3,1) (3,2) (3,3) … (3,M)

… … … … … …

N (N,1) (N,2) (N,3) … (N,M)

现在已知有一个恐怖组织在其中的一个街区安放了定时炸弹，其威力为T，即所有到这个街区的直线距离小于等于T的街区都会受威胁，已知有K个可能的炸弹安放位置，现在这里的警长想知道最坏的情况下会有多少街区受威胁。

输入输出格式

输入格式：

第一行四个正整数N，M，K和T

接下来K行每行两个正整数Xi Yi，描述每个可能安放炸弹的街区。

输出格式：

一个正整数为在最坏情况下有多少街区会受威胁。

输入输出样例

输入样例#1：

输出样例#1：

说明

对于20%的数据 K=1

对于50%的数据 N，M≤1000 K≤20 T≤100

对于100%的数据 N，M≤100000 K≤50 T≤300

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
bool vis[1100][1100];
int n,m,k,t,x,y,ans;
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();}
    return x*f;
}
void dfs(int x,int y,int s)
{
    if(s==t+1) return ;
    if(vis[x][y]||x<1||y<1||x>n||y>m) return ;
    vis[x][y]=true;
    if(s!=0) ans++;
    for(int i=0;i<4;i++)
    {
        int fx=x+xx[i],fy=y+yy[i];
        dfs(fx,fy,s+1);    
    }
    //vis[x][y]=false;
}
int main()
{
    n=read(),m=read();
    k=read(),t=read();
    for(int i=1;i<=k;i++)
    {
        x=read(),y=read();
        if(vis[x][y]) ans--;
        dfs(x,y,0);
     } 
    printf("%d",ans);
    return 0;
}

本来是想练练搜索的，结果发现我根本就不会写这个搜索、、、、

暴力枚举在那个位置放炸弹的造成的最大危险

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
bool vis[11000][11000];
int n,m,k,t,x,y,ans;
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();}
    return x*f;
}
bool work(int x,int y,int fx,int fy)
{
    if(sqrt(pow(x-fx,2)+pow(y-fy,2))<=t) return true;
    return false;
}
int main()
{
    n=read(),m=read();
    k=read(),t=read();
    while(k--)
    {
        x=read(),y=read();
        int sum=0;
        for(int i=max(1,x-t);i<=min(n,x+t);i++)
         for(int j=max(1,y-t);j<=min(m,y+t);j++)
          { 
            if(work(i,j,x,y)) sum++;
          } 
        ans=max(ans,sum);
    } 
    printf("%d",ans);
    return 0;
}

洛谷p3393逃离僵尸岛

题目描述小a住的国家被僵尸侵略了！小a打算逃离到该国唯一的国际空港逃出这个国家。该国有N个城市，城市之间有道路相连。一共有M条双向道路。保证没有自环和重边。K个城市已经被僵尸控制了，如果贸然闯入就会被感... 查看详情

洛谷——p1690贪婪的copy

https://www.luogu.org/problem/show?pid=1690题目描述Copy从卢牛那里听说在一片叫yz的神的领域埋藏着不少宝藏，于是Copy来到了这个被划分为个区域的神地。卢牛告诉了Copy这里共有个宝藏，分别放在第Pi个(1<=Pi<=N)区域。Copy还得知了每... 查看详情

洛谷——p1690贪婪的copy

P1690贪婪的Copy题目描述Copy从卢牛那里听说在一片叫yz的神的领域埋藏着不少宝藏，于是Copy来到了这个被划分为个区域的神地。卢牛告诉了Copy这里共有个宝藏，分别放在第Pi个(1<=Pi<=N)区域。Copy还得知了每个区域之间的距离。... 查看详情

洛谷p1690贪婪的copy

洛谷p1434滑雪

题目描述Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二... 查看详情

洛谷——p1434滑雪

https://www.luogu.org/problem/show?pid=1434#sub题目描述Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一... 查看详情

搜索洛谷p1434滑雪

P1434滑雪题目描述Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。... 查看详情

洛谷p1047校门外的树

P1047校门外的树题目描述某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……... 查看详情

洛谷——p2121拆地毯

P2121拆地毯题目背景还记得NOIP2011提高组Day1中的铺地毯吗？时光飞逝，光阴荏苒，三年过去了。组织者精心准备的颁奖典礼早已结束，留下的则是被人们踩过的地毯。请你来解决类似于铺地毯的另一个问题。题目描述会场上有n个... 查看详情

bsoj3760||洛谷p1453城市环路题解

城市环路Description　　一座城市，往往会被人们划分为几个区域，例如住宅区、商业区、工业区等等。B市就被分为了以下的两个区域——城市中心和城市郊区。在着这两个区域的中间是一条围绕B市的环路，环路之内便是B... 查看详情

洛谷⑨月月赛round2p3393逃离僵尸岛[最短路]

题目描述小a住的国家被僵尸侵略了！小a打算逃离到该国唯一的国际空港逃出这个国家。该国有N个城市，城市之间有道路相连。一共有M条双向道路。保证没有自环和重边。K个城市已经被僵尸控制了，如果贸然闯入就会被感染TAT.... 查看详情

洛谷p1927防护伞

P1927防护伞题目描述据说2012的灾难和太阳黑子的爆发有关。于是地球防卫小队决定制造一个特殊防护伞，挡住太阳黑子爆发的区域，减少其对地球的影响。由于太阳相对于地球来说实在是太大了，我们可以把太阳表面看作一个平... 查看详情

洛谷p1510精卫填海(代码片段)

　　　　　　　　　　　　洛谷P1510精卫填海题目描述【版权说明】本题为改编题。【问题描述】发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海... 查看详情

洛谷p1506拯救oibh总部(代码片段)

　　　　　　　　　　　　　　　　　　　　洛谷P1506拯救oibh总部题目背景oibh总部突然被水淹没了！现在需要你的救援……题目描述oibh被突来的洪水淹没了>.<还好oibh总部有在某些重要的地方起一些围墙，用*号表示，... 查看详情

地铁间谍（洛谷2583）

题目描述特工玛利亚被送到S市执行一个特别危险的任务。她需要利用地铁完成他的任务，S市的地铁只有一条线路运行，所以并不复杂。玛利亚有一个任务，现在的时间为0，她要从第一个站出发，并在最后一站的间谍碰头。玛利... 查看详情

洛谷p1510精卫填海

P1510精卫填海题目描述【版权说明】本题为改编题。【问题描述】发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海，溺而不返，故为精卫。常衔西... 查看详情

洛谷p1250种树（贪心）

题目描述一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个... 查看详情

洛谷p2704noi2001炮兵阵地

题目描述司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H”表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮... 查看详情