热门标签 | 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);
}

 原文链接


推荐阅读
  • 本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率,使用经典的EK(Edmonds-Karp)和Dinic算法进行求解。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • Linux环境下进程间通信:深入解析信号机制
    本文详细探讨了Linux系统中信号的生命周期,从信号生成到处理函数执行完毕的全过程,并介绍了信号编程中的注意事项和常见应用实例。通过分析信号在进程中的注册、注销及处理过程,帮助读者理解如何高效利用信号进行进程间通信。 ... [详细]
  • 本文介绍了一个项目中如何在Windows平台上实现多声道音频数据的采集,特别是针对DANTE音频接口的8路立体声音频通道。文章详细描述了使用Windows底层音频API进行音频采集的方法,并提供了一个具体的实现示例。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本题涉及一棵由N个节点组成的树(共有N-1条边),初始时所有节点均为白色。题目要求处理两种操作:一是改变某个节点的颜色(从白变黑或从黑变白);二是查询从根节点到指定节点路径上的第一个黑色节点,若无则输出-1。 ... [详细]
  • Codeforces Round #566 (Div. 2) A~F个人题解
    Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意:给你一个的表格,你 ... [详细]
  • 在进行QT交叉编译时,可能会遇到与目标架构不匹配的宏定义问题。例如,当为ARM或MIPS架构编译时,需要确保使用正确的宏(如QT_ARCH_ARM或QT_ARCH_MIPS),而不是默认的QT_ARCH_I386。本文将详细介绍如何正确配置编译环境以避免此类错误。 ... [详细]
  • Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • 本题通过将每个矩形视为一个节点,根据其相对位置构建拓扑图,并利用深度优先搜索(DFS)或状态压缩动态规划(DP)求解最小涂色次数。本文详细解析了该问题的建模思路与算法实现。 ... [详细]
  • cJinja:C++编写的轻量级HTML模板引擎
    本文介绍了cJinja,这是一个用C++编写的轻量级HTML模板解析库。它利用ejson来处理模板中的数据替换(即上下文),其语法与Django Jinja非常相似,功能强大且易于学习。 ... [详细]
  • QNX 微内核(procnto-instr)的监测版本内置了高级跟踪与分析工具,能够实现实时系统监控。该模块适用于单处理器及多处理器系统。 ... [详细]
  • 本文详细介绍了如何通过修改Lua源码或使用动态链接库(DLL)的方式实现Lua与C++之间的高级交互,包括如何编译Lua源码、添加自定义API以及在C++中加载和调用Lua脚本。 ... [详细]
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社区 版权所有