nyoj 547 优先队列
#include<stdio.h>
#include<string.h>
#include<queue>//水杯盛水问题,用优先队列不断从最小的边缘开始
using namespace std;
int n,m;
#define N 400
int p[N][N];
struct node {
int x,y,w;
friend bool operator<(node a,node b) {//优先队列
return a.w>b.w;//从小到大出队
}
};
int visit[N][N];
int dis[4][2]={1,0,0,1,-1,0,0,-1};//四个方向
int judge(int x,int y) {
if(x<=n&&x>=1&&y<=m&&y>=1&&!visit[x][y])
return 1;
return 0;
}
int main() {
int i,j,sum;
while(scanf("%d%d",&m,&n)!=EOF) {
priority_queue<node>q;
node cur,next;
memset(visit,0,sizeof(visit));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) {
scanf("%d",&p[i][j]);
if(j==1||j==m||i==1||i==n) {//先将杯子的边缘加入
cur.x=i;cur.y=j;
cur.w=p[i][j];
visit[i][j]=1;//标记边缘不能搜索
q.push(cur);
}
}
sum=0;
while(!q.empty()) {//每次从最小的边缘开始
cur=q.top();
q.pop();
for(i=0;i<4;i++) {
int xx=next.x=cur.x+dis[i][0];
int yy=next.y=cur.y+dis[i][1];
if(judge(xx,yy)) {//判断
visit[xx][yy]=1;
if(p[xx][yy]<cur.w) {//如果当前的边缘大于水杯内部
sum+=cur.w-p[xx][yy];//高度差即为所能盛的水
next.w=cur.w;//改变当前点值
q.push(next);
}
else {//
next.w=p[xx][yy];/
q.push(next);//
}
}
}
}
printf("%d\n",sum);//
}
return 0;
}
最新文章
- OGG-01820 Could not enable workspace
- 十天学会DIV+CSS(DIV布局)
- php中的可变函数和匿名函数
- symfony2 controller
- Titanium开发环境搭建第三个坑
- C#&;java重学笔记(泛型)
- [HDU] 2094 产生冠军(拓扑排序+map)
- iOS 任意类型数据转换字符串
- STM32F4XX与STM32F0XX编程差别
- 201521123004《Java程序设计》第9周学习总结
- 一秒搞定mysql的远程登录
- 后端分布式系列:分布式存储-HDFS Client 设计实现解析
- yii2 数据提供者 dataProvider
- Express4.x API (三):Response (译)
- 20155210 Exp2 后门原理与实践
- MongoDB - MongoDB CRUD Operations, Query Documents, Query for Null or Missing Fields
- SQLServer 2008中SQL增强之三 Merge(在一条语句中使用
- Web前端页面的浏览器兼容性测试心得(一)搭建测试用本地静态服务器
- salt总结
- 九度OJ 1351:数组中只出现一次的数字 (位运算)
热门文章
- Pointcut is not well-formed: expecting &;#39;name pattern&;#39; at character position 36
- 一段程序的人生 第10章: server
- 摄像头ov2685中关于sensor id 设置的相关的寄存器地址【转】
- Python 33(1) UDP协议 数据报协议 socketsever模块
- 【LuoguP5004】 专心OI - 跳房子
- 【寒假集训系列DAY.1】
- ROS-导航功能-Gazebo
- Mysql 时间、字符串、时间戳互转
- Md2All,把图片轻松上传到云图床,自动生成Markdown
- react基础篇二