草庐IT

POJ 2227 The Wedding Juicer（三维接雨水 BFS 贪心

DM11 2023-03-28 原文

POJ 2227 The Wedding Juicer（三维接雨水 BFS 贪心）

题意：

​ 给出一个二维地图，其各点上权值为其高度。如果向其中填水，请问在这张地图中可以积得多少水。

​ 地图长宽为300,高度最高为1e9。

999							
919										
989 以此图为例，可积水7

思路：

​ 通过观察所给样例，可以发现，整个地图的储水量取决于最外围的最矮的点。若这个最矮的点被其周围比其高的点挡住，那边界就从这个最矮的点变成了其周围最矮的点。若最矮的点周围还有更矮的点，那他可以积的水为这两点的差值，同样更新一下边界。

​ 那么我们程序化这个过程，将最外一圈放入小根堆中，然后BFS扩展，根据两种情况来更新我们的边界，同时累积水。因为最矮的点是积水的短板，所以每次优先处理它。

实现：

​ 防重走，还有很坑爹的n和m是反的。

int n, m;
int a[305][305];
long long res = 0;
int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int vis[305][305];

struct node {
    int x, y, val;
    node(int x_, int y_, int _val) {x = x_, y = y_, val = _val;}
    bool operator < (const node &a) const {
        return val > a.val;
    }
};

int main()
{
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            scanf("%d", &a[i][j]);
    
    priority_queue<node> q;
    for(int i = 1; i <= n; i ++)
    {
        vis[i][1] = vis[i][m] = 1;
        q.push(node(i, 1, a[i][1]));
        q.push(node(i, m, a[i][m]));
    }
    for(int i = 2; i <= m - 1; i ++)
    {
        vis[1][i] = vis[n][i] = 1;
        q.push(node(1, i, a[1][i]));
        q.push(node(n, i, a[n][i]));
    }

    while(q.size())
    {
        node tmp = q.top();
        q.pop();

        for(int i = 0; i < 4; i ++)
        {
            int xx = tmp.x + d[i][0], yy = tmp.y + d[i][1];
            if(vis[xx][yy]) continue;
            if(xx > n || xx < 1 || yy > m || yy < 1)    continue;
            if(a[xx][yy] >= tmp.val)
                q.push(node(xx, yy, a[xx][yy]));
            else
                q.push(node(xx, yy, tmp.val)), res += (tmp.val - a[xx][yy]);
            vis[xx][yy] = 1;
        }
    }
    printf("%lld\n", res);
}
WeddingJuicerintnodeval算法与数据结构

有关POJ 2227 The Wedding Juicer（三维接雨水 BFS 贪心的更多相关文章

  1. NEUQ-acm 预备队训练Week4—BFS/DFS - 2

    1.深度优先搜索(DFS)深度优先遍历主要思路是从图中一个未访问的顶点V开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成。例题P1605迷宫题目描述给定一个N×MN\timesMN×M方格的迷宫，迷宫里有TTT处障碍，障碍处不可通过。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。输入格式第一行为三个正整数N,M,TN,M,TN,M,T，分别表示迷宫的长宽和障碍总数。第二行为四个正整数SX,S

  2. 常见搜索模板DFS+BFS+二分搜索【算法】 - 2

     本篇讲的是常见的搜索模板，搜索题的解法时比较固定的，只要把模板记熟，加上自己找几道习题练习体会后，相信各位下次遇到这类题一定能拿下！！下面我将已典型的题目为例子介绍几种常见的搜索方式。 1.二分搜索二分搜索代码模板：例题：#includeusingnamespacestd;doublen;constdoubleeps=1e-12;//二分搜索intmain(){ intt; cin>>t; while(t--){ cin>>n; doublel=0,r=100000,res=-1; while(ln)r=mid-0.0001; elseif(mid*mid*mid二分搜索是只能对有

  3. 视频融合技术解决方案，三维全景拼接赋能平台 - 2

    近年来，随着信息化时代的到来，三维全景拼接以视频监控领域为代表的智能硬件公司迅速崛起，随后全国各地在视频监控领域进行了大量的建设。但随着摄像头数量的增加，视频监控画面离散、庞杂、关联性差等诸多问题日渐凸显。如何优化现有视频技术，助力管理者或使用者有效、直观、准确地掌控现场实时动态，成为我国信息化前行路上面临的新课题。视频融合技术平台解决方案北京智汇云舟科技有限公司成立于2012年，专注于创新性的“视频孪生（实时实景数字孪生）”技术研发与应用。公司依托自研三维地理信息引擎（3DGIS），融合建筑信息模型（BIM）、视频监控（Video）、人工智能（AI）及物联网（IOT）等多种技术，并在此基础上

  4. 华为OD机试题 Q2 押题【贪心的商人 or 最大利润】用 C++ 编码，速通 - 2

    最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试，独家整理已参加机试人员的实战技巧本篇题解：贪心的商人or最大利润题目描述商人经营一家店铺，有number种商品，由于仓库限制每件商品的最大持有数量是item[index]，每种商品的价格在每天是item_price[item_index][day]，通过对商品的买进和卖出获取利润，请给出商人在days天内能获取到的最大的利润；注：同一件商品可以反复买进和卖出；输入描述3//输入商品的数量nu

  5. DJI Pilot无人机航线规划-实景三维建模全流程 - 2

    目前很多网上推荐的无人机航线规划软件如Altizure、航测通等难以下载或为商用软件。该文章以大疆精灵4为例演示DJIPilot航线规划-CC实景建模-三维模型导入Cesiumlab3全流程。目录一、软件准备二、DJIPilot航线规划1、准备工作1.1了解测区环境1.2检查无人机2、航线规划2.1创建测绘区域2.2参数设置3、执行飞行任务三、CC实景建模1.1创建工程1.2添加影像1.3影像设置1.4提交空中三角测量1.5空间框架参数设置四、在cesiumlab3上导入三维模型2.1OSGB格式转为3Dtiles2.2导入3D模型附录：1、GSD2.不同区域像控点选取：3、奥维地图在测绘作业

  6. 三维点云| CloudCompare软件使用总结 - 2

    一、Fileopen：打开文件save：保存应用实例：CloudCompare——laz与las格式点云相互转换及代码实现https://blog.csdn.net/qq_36686437/article/details/119945199GlobalShiftsettings：设置最大绝对坐标，最大实体对角线PrimitiveFactory：生成三维几何体模型应用实例：CloudCompare——生成常见几何点云https://blog.csdn.net/qq_36686437/article/details/1200091303Dmouse：对3D鼠标（如3Dconnexion）的支持Cl

  7. 迷宫问题-DFS-BFS - 2

    迷宫问题迷宫问题简介BFS解决迷宫最短路径问题DFS记录迷宫路径DFS解决迷宫所有路径问题迷宫问题简介🚀学习过算法程序设计的应该都学习过迷宫这个问题，迷宫问题主要设计的算法就是DFS-深度优先遍历和BFS-广度优先遍历。🚀在一个二维数组中，元素为1的位置表示这个位置是墙，0表示有通路，迷宫的入口和出口都是0（否则不会有路径能出去），并且路径不唯一。例如下图：🚀图中这个迷宫有两条路径，分别用粉色和蓝色标记了出来，明显粉色路径的长度是比蓝色路径要短的。BFS解决迷宫最短路径问题🚀BFS可以解决最短路径的原因是，BFS是像水波一样逐渐向外圈波及的，很明显最先波及到的通路就是最短路径。🚀使用BFS算法

  8. 深度学习三维图像数据增强——Monai实现 - 2

    深度学习三维图像数据增强——Monai实现一、前言二、数据类型三、Compose四、OneOf五、常见转换类型5.1裁减和填充5.2强度增强5.3空间增强六、注意（记录坑）6.1RandRotate90一、前言笔者接触深度学习不久，跑过一些二维图像的深度学习代码，对于二维图像，深度学习数据增强可借助skimage、opencv、imgaug、Albumentations、Augmentor等多数主流的库实现，在这里放一个大神的链接，可供参考。但对于三维数据，能够借助的库便少了起来，常用的有TorchIO和Monai，而针对于医学领域，Monai是一个不错的选择。笔者通过自学，将Monia库总结

  9. 【独家】华为OD机试 - 贪心的商人 or 最大利润（C 语言解题） - 2

    最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试，独家整理已参加机试人员的实战技巧本篇题解：贪心的商人or最大利润题目描述商人经营一家店铺，有number种商品，由于仓库限制每件商品的最大持有数量是item[index]，每种商品的价格在每天是item_price[item_index][day]，通过对商品的买进和卖出获取利润，请给出商人在days天内能获取到的最大的利润；注：同一件商品可以反复买进和卖出；输入描述3//输入商品的数量nu

  10. 【算法刷题】贪心算法题型及方法归纳 - 2

    贪心算法特点从局部最优解推出全局最优，并且想不出来反例。贪心没有明确有规律的套路，而对于贪心的难题，更多的是难在思路上，要用一些转化问题的思维方法，然后，再根据局部最优解推出全局最优。参考文章：贪心算法理论基础1、发饼干先排序，按饼干从小到大的顺序，依次分给从小到大排序的小朋友。127、【贪心算法】leetcode——455.分发饼干：DFS+双指针法（C++版本）2、0水准线count用来记录当前子序列的相加和，当count大于0时，继续相加。当count小于或等于0时，重新开始选取子序列。以count是否为0判定的原因：若后续为正数时，没有这个负数更好，若后续为负数时，越加只会越小）129

随机推荐