POJ2227总结

The Wedding Juicer

题目来源

Description

Farmer John’s cows have taken a side job designing interesting punch-bowl designs. The designs are created as follows:

• A flat board of size W cm x H cm is procured (3 <= W <= 300, 3 <= H <= 300)
• On every 1 cm x 1 cm square of the board, a 1 cm x 1 cm block is placed. This block has some integer height B (1 <= B <= 1,000,000,000)

The blocks are all glued together carefully so that punch will not drain through them. They are glued so well, in fact, that the corner blocks really don’t matter!

FJ’s cows can never figure out, however, just how much punch their bowl designs will hold. Presuming the bowl is freestanding (i.e., no special walls around the bowl), calculate how much juice the bowl can hold. Some juice bowls, of course, leak out all the juice on the edges and will hold 0.

Input

* Line 1: Two space-separated integers, W and H

* Lines 2..H+1: Line i+1 contains row i of bowl heights: W space-separated integers each of which represents the height B of a square in the bowl. The first integer is the height of column 1, the second integers is the height of column 2, and so on.

Output

* Line 1: A single integer that is the number of cc’s the described bowl will hold.

Sample Input

4 5
5 8 7 7
5 2 1 5
7 1 7 1
8 9 6 9
9 8 9 9

Sample Output

12

Hint

OUTPUT DETAILS:

Fill-up the two squares of height 1 to height 5, for 4 cc for each square. Fill the square of height 2 to height 5, for 3 cc of joice. Fill the square of height 6 to height 7 for 1 cc of juice. 2*4 + 3 + 1 = 12.

我的代码

利用优先队列，队列里面存储的都是边界值，即队首的高度就是剩下来的方块的高度可以达到的最小值。每次遍历队首元素的周围四个方块，更新其高度后加入队列。如果一个方块被更新，说明其可以容纳水，即需要更新答案。

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
struct grid
{
	int x,y;
	int hight;
	
	bool operator<(const grid &a)const
	{
		return hight>a.hight;
	}
	
	grid(int x,int y,int hight):x(x),y(y),hight(hight){}
};

int w,h;
long long int ans=0;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool in (int x,int y)
{
	return x>=1&&x<=h&&y>=1&&y<=w;
}
int main()
{
	
	int grids[310][310];
	int visit[310][310]={0};
	priority_queue<grid>q;
	while(!q.empty())
	q.pop();
	scanf("%d%d",&w,&h);
	for (int i=1;i<=h;i++)
	{
		for (int j=1;j<=w;j++)
		{
			scanf("%d",&grids[i][j]);
			if ((i==1||i==h)||(j==1||j==w))
			{
				q.push(grid(i,j,grids[i][j]));
				visit[i][j]=1;
			}
		}
	}
	while(!q.empty())
	{
		grid t=q.top();
		q.pop();
		for (int d=0;d<4;d++)
		{
			int x=t.x+dir[d][0];
			int y=t.y+dir[d][1];
			if (in(x,y))
			{
				if (visit[x][y]==0)
				{
					if (grids[x][y]<t.hight)
					{
						//printf("%d %d: %d->%d\n",x,y,grids[x][y],t.hight);
						ans+=t.hight-grids[x][y];
						grids[x][y]=t.hight;
						
					}
					q.push(grid(x,y,grids[x][y]));
					visit[x][y]=1;
				}
			}
		}
	}
	printf("%lld",ans);
	return 0;
}

反思

知道用优先队列，但是思路错了。