2350.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2350 on 2006-09-09 at 10:40:07 */ 
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
typedef long long int64;
const int N = 320;
const int DIR[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
 
class Block {
public:
	int x, y, h;
	Block(int cx, int cy, int ch) : x(cx), y(cy), h(ch) {}
	bool operator >(const Block& b) const { return h > b.h; }
};
 
int w, h, map[N][N];
bool vst[N][N];
 
int64 rain();
int64 bfs(Block&);
bool legal(int x, int y) { return x >= 0 && x < h && y >= 0 && y < w && !vst[x][y]; }
 
priority_queue< Block, vector<Block>, greater<Block> > Q;
 
int main()
{
	while(scanf("%d %d", &w, &h) != EOF) {
		for(int i = 0; i < h; i++)
			for(int j = 0; j < w; j++) scanf("%d", &map[i][j]);
		printf("%lld\n", rain());
	}
	
	return 0;
}
 
int64 rain()
{
	memset(vst, false, sizeof(vst));
	while(!Q.empty()) Q.pop();
	for(int i = 0; i < h; i++) {
		Q.push(Block(i, 0, map[i][0])); vst[i][0] = true;
		Q.push(Block(i, w-1, map[i][w-1])); vst[i][w-1] = true;
	}
	for(int i = 0; i < w; i++) {
		Q.push(Block(0, i, map[0][i])); vst[0][i] = true;
		Q.push(Block(h-1, i, map[h-1][i])); vst[h-1][i] = true;
	}
	int64 r = 0;
	while(!Q.empty()) {
		Block b = Q.top(); Q.pop();
		r += bfs(b);
	}
	return r;
}
int64 bfs(Block& b)
{
	int64 r = 0;
	vst[b.x][b.y] = true;
	queue<int> Qb; Qb.push((b.x<<10)|b.y);
	while(!Qb.empty()) {
		int p = Qb.front(); Qb.pop();
		int x = p>>10, y = p&1023;
		for(int i = 0; i < 4; i++) {
			int cx = x+DIR[i][0], cy = y+DIR[i][1];
			if(!legal(cx, cy)) continue;
			vst[cx][cy] = true;
			if(map[cx][cy] < b.h) { r += b.h-map[cx][cy]; Qb.push((cx<<10)|cy); }
			else Q.push(Block(cx, cy, map[cx][cy]));
		}
	}
	
	return r;
}