文档章节

Interesting Punch-Bowl(优先队列)

1
 1944864971
发布于 2016/07/24 11:58
字数 408
阅读 2
收藏 0

/**
http://acm.nyist.net/JudgeOnline/problem.php?pid=547
题意:
有一个正方形的区域 区域上面有高度不同的1*1的立方体自然有凸有凹
凹的地方可以储水
问一共可以储存多少水

分析:
每次都从最低的边界向内部注水(仅与边界相邻的内部)
如果能够注水 就把注水后的柱子当作新的边界
也就是把边界放到一个优先队列中 每次都让高度最小的边界出队(优先队列)

*/

include

include

include

using namespace std;
int n,m,sum=0;
int bowl[350][350];
int vis[350][350];
int dir[4][2]= {0,1,1,0,0,-1,-1,0};
struct node
{
int x;
int y;
int h;
friend bool operator <(node a,node b)
{
return a.h>b.h;
}
};
priority_queue q;
void chuShiHua()///首先把边界放入队列中
{
memset(vis,0,sizeof(vis));
node b;
for(int i=1; i<=m; i++)
{
b.x=i;
b.y=1;
b.h=bowl[i][1];
vis[i][1]=1;
q.push(b);
b.x=i;
b.y=n;
b.h=bowl[i][n];
vis[i][n]=1;
q.push(b);
}
for(int i=2; i<=n-1; i++)
{
b.x=1;
b.y=i;
b.h=bowl[1][i];
vis[1][i]=1;
q.push(b);
b.x=m;
b.y=i;
b.h=bowl[m][i];
vis[m][i]=1;
q.push(b);
}
}

void bfs()
{
chuShiHua();
while(!q.empty())
{
node a,b;
a=q.top();

    q.pop();
    for(int i=0; i<4; i++)
    {
        int x=a.x+dir[i][0];
        int y=a.y+dir[i][1];
        if(x<1||x>m||y<1||y>n)
            continue;

        if(vis[x][y]==0)
        {
            if(bowl[x][y]<a.h)///可以向内部注水
            {

                sum+=a.h-bowl[x][y];
                b.x=x;
                b.y=y;
                b.h=a.h;
                vis[x][y]=1;
                q.push(b);
            }
            else///不可以
            {
                b.x=x;
                b.y=y;
                b.h=bowl[x][y];
                vis[x][y]=1;
                q.push(b);

            }
        }
    }

}

}

int main()
{
while(~scanf("%d%d",&n,&m))
{

    memset(bowl,0,sizeof(bowl));
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            scanf("%d",&bowl[i][j]);
    sum=0;
    bfs();
    printf("%d\n",sum);
}
return 0;

}

本文转载自:http://www.cnblogs.com/aaaadengchaochao/p/5502315.html

1
粉丝 0
博文 57
码字总数 0
作品 0
郑州
私信 提问
JavaScript数据结构03 - 队列

一、定义 前面我们学习了栈的实现,队列和栈非常类似,但是使用了不同的原则,而非后进先出。 队列是遵循FIFO(First In First Out,先进先出)原则的一组有序的项。队列在尾部添加新元素,并...

leocoder
2018/07/26
0
0
STL之优先队列

上一篇优先队列实现讲述如何使用最大堆来自己实现一个优先队列,实际上STL里面也为我们提供了相关的实现。下面具体来看一下STL中优先队列的使用方法。 基本定义 STL中定义优先队列的类为pri...

xinyuexy
2017/11/27
0
0
JavaScript数据结构之 - 队列

前面我们学习了栈的实现,队列和栈非常类似,但是使用了不同的原则,而非后进先出。 队列是遵循FIFO(First In First Out,先进先出)原则的一组有序的项。队列在尾部添加新元素,并从顶部移...

小刀爱编程
2018/10/29
4
0
Java PriorityQueue && PriorityBlockingQueue

Java PriorityQueue && PriorityBlockingQueue 我们知道队列是遵循先进先出(First-In-First-Out)模式的,但有些时候需要在队列中基于优先级处理对象。举个例子,比方说我们有一个每日交易时...

秋风醉了
2015/01/12
191
0
Java优先队列(PriorityQueue)示例

我们知道队列是遵循先进先出(First-In-First-Out)模式的,但有些时候需要在队列中基于优先级处理对象。举个例子,比方说我们有一个每日交易时段生成股票报告的应用程序,需要处理大量数据并...

wx5955e325d6bfb
2017/07/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

分布式协调服务zookeeper

ps.本文为《从Paxos到Zookeeper 分布式一致性原理与实践》笔记之一 ZooKeeper ZooKeeper曾是Apache Hadoop的一个子项目,是一个典型的分布式数据一致性的解决方案,分布式应用程序可以基于它...

ls_cherish
今天
4
0
redis 学习2

网站 启动 服务端 启动redis 服务端 在redis 安装目录下 src 里面 ./redis-server & 可以指定 配置文件或者端口 客户端 在 redis 的安装目录里面的 src 里面 ./redis-cli 可以指定 指定 连接...

之渊
昨天
2
0
Spring boot 静态资源访问

0. 两个配置 spring.mvc.static-path-patternspring.resources.static-locations 1. application中需要先行的两个配置项 1.1 spring.mvc.static-path-pattern 这个配置项是告诉springboo......

moon888
昨天
4
0
hash slot(虚拟桶)

在分布式集群中,如何保证相同请求落到相同的机器上,并且后面的集群机器可以尽可能的均分请求,并且当扩容或down机的情况下能对原有集群影响最小。 round robin算法:是把数据mod后直接映射...

李朝强
昨天
4
0
Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
昨天
24
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部