热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

USACO2008NovSilver2.GuardingtheFarm

2593:USACO2008NovSilver2.GuardingtheFarm题目描述ThefarmhasmanyhillsuponwhichFarmerJoh

2593: USACO 2008 Nov Silver 2.Guarding the Farm

题目描述

The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows.

He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1

A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.

农场里有许多山丘,在山丘上约翰要设置哨岗来保卫他的价值连城的奶牛.

约翰不知道有多少山丘,也就不知道要设置多少哨岗.他有一张地图,用整数矩阵的方式描 述了农场N(1 <= N<=700)行M(1

一个山丘是指某一个方格,与之相邻的方格的海拔高度均严格小于它.当然,与它相邻的方 格可以是上下左右的那四个,也可以是对角线上相邻的四个.

输入输出格式

输入格式:

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 describes row i of the matrix with M

space-separated integers: H_ij

输出格式:

* Line 1: A single integer that specifies the number of hilltops

思路:地图题,不解释,上代码

#include 
#include 
#include 
#include 
using namespace std;
struct node
{
    int x,y,h;
}a[500000];
int mx[8]={0,0,1,1,1,-1,-1,-1};
int my[8]={-1,1,-1,0,1,-1,0,1};
bool cmp(const node &a,const node &b)
{
    return a.h==b.h?a.xb.h;
}
bool vis[701][701];
int cnt;
int n,m;
int map[701][701];
queueq;
void bfs(int now)
{
    q.push((node){a[now].x,a[now].y,0});
    vis[a[now].x][a[now].y]=1;
    while(!q.empty())
    {
        node u=q.front();
        q.pop();
        int xx=u.x,yy=u.y,hh=map[xx][yy];
        for(int i=0;i<8;i++)
        {
            int tx=xx+mx[i],ty=yy+my[i];
            if(tx<=0||ty<=0||tx>n||ty>m)
                continue;
            if(hh>=map[tx][ty]&&!vis[tx][ty])
            {
                vis[tx][ty]=1;
                q.push((node){tx,ty,0});
            }
        }
    }
}
int main()
{
     
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&map[i][j]);
            a[++cnt].x=i,a[cnt].y=j,a[cnt].h=map[i][j];
        }
    }
    int ans=0;
    sort(a+1,a+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
    {
        if(!vis[a[i].x][a[i].y]&&a[i].h!=0)
        {
            ans++;
            //printf("%d %d\n",a[i].x,a[i].y);
            bfs(i);
        }
    }
    printf("%d",ans);
}

 原文链接


推荐阅读
  • 本文探讨了如何通过预处理器开关选择不同的类实现,并解决在特定情况下遇到的链接器错误。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • 前言--页数多了以后需要指定到某一页(只做了功能,样式没有细调)html ... [详细]
  • 本文介绍如何在现有网络中部署基于Linux系统的透明防火墙(网桥模式),以实现灵活的时间段控制、流量限制等功能。通过详细的步骤和配置说明,确保内部网络的安全性和稳定性。 ... [详细]
  • Hadoop发行版本选择指南:技术解析与应用实践
    本文详细介绍了Hadoop的不同发行版本及其特点,帮助读者根据实际需求选择最合适的Hadoop版本。内容涵盖Apache Hadoop、Cloudera CDH等主流版本的特性及应用场景。 ... [详细]
  • 由中科院自动化所、中科院大学及南昌大学联合研究提出了一种新颖的双路径生成对抗网络(TP-GAN),该技术能通过单一侧面照片生成逼真的正面人脸图像,显著提升了不同姿态下的人脸识别效果。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • Explore a common issue encountered when implementing an OAuth 1.0a API, specifically the inability to encode null objects and how to resolve it. ... [详细]
  • Java 中的 BigDecimal pow()方法,示例 ... [详细]
  • 本文介绍如何利用动态规划算法解决经典的0-1背包问题。通过具体实例和代码实现,详细解释了在给定容量的背包中选择若干物品以最大化总价值的过程。 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
author-avatar
马里奥毛瑞尔小P
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有