pku2227.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <algorithm>
#include <string.h>
#define size 310
using namespace std;

typedef struct Node
{
	int x, y;
} Node;

Node heap[size * size];
int h[size][size];
bool v[size][size];
int W, H, end;
int Dis[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

bool cmp(const Node &a, const Node &b)
{
	return h[a.x][a.y] > h[b.x][b.y];
}

bool In(const int x, const int y)
{
	return x >= 0 && x < H && y >= 0 && y < W;
}

void Solve()
{
	int i, j, nx, ny, x, y;
	int ans = 0;
	end = 0;
	memset(v, 0, sizeof(v));
	for (i = 0; i < H; i++)
	{
		for (j = 0; j < W; j++)
		{
			scanf("%d", &h[i][j]);
			if (i == 0 || j == 0 || i == H - 1 || j == W - 1)
			{
				heap[end].x = i;
				heap[end].y = j;
				v[i][j] = 1;
				end++;
				push_heap(heap, heap + end, cmp);
			}
		}
	}
	do
	{
		x = heap[0].x;
		y = heap[0].y;
		pop_heap(heap, heap + end, cmp);
		end--;
		for (i = 0; i < 4; i++)
		{
			nx = x + Dis[i][0];
			ny = y + Dis[i][1];
			if (In(nx, ny) && !v[nx][ny])
			{
				if (h[nx][ny] < h[x][y])
				{
					ans += h[x][y] - h[nx][ny];
					h[nx][ny] = h[x][y];
				}
				v[nx][ny] = 1;
				heap[end].x = nx;
				heap[end].y = ny;
				end++;
				push_heap(heap, heap + end, cmp);
			}
		}
	}
	while (end);
	printf("%d\n", ans);
}



int main()
{
	while (scanf("%d %d", &W, &H) != -1)
	{
		Solve();
	}
	return 0;
}