POJ 2227 The Wedding Juicer（三维接雨水 BFS 贪心）
题意：
给出一个二维地图，其各点上权值为其高度。如果向其中填水，请问在这张地图中可以积得多少水。
地图长宽为300,高度最高为1e9。
999
919
989 以此图为例，可积水7
思路：
通过观察所给样例，可以发现，整个地图的储水量取决于最外围的最矮的点。若这个最矮的点被其周围比其高的点挡住，那边界就从这个最矮的点变成了其周围最矮的点。若最矮的点周围还有更矮的点，那他可以积的水为这两点的差值，同样更新一下边界。
那么我们程序化这个过程，将最外一圈放入小根堆中，然后BFS扩展，根据两种情况来更新我们的边界，同时累积水。因为最矮的点是积水的短板，所以每次优先处理它。
实现：
防重走，还有很坑爹的n和m是反的。
int n, m;
int a[305][305];
long long res = 0;
int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int vis[305][305];
struct node {
int x, y, val;
node(int x_, int y_, int _val) {x = x_, y = y_, val = _val;}
bool operator < (const node &a) const {
return val > a.val;
}
};
int main()
{
scanf("%d%d", &m, &n);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
scanf("%d", &a[i][j]);
priority_queue<node> q;
for(int i = 1; i <= n; i ++)
{
vis[i][1] = vis[i][m] = 1;
q.push(node(i, 1, a[i][1]));
q.push(node(i, m, a[i][m]));
}
for(int i = 2; i <= m - 1; i ++)
{
vis[1][i] = vis[n][i] = 1;
q.push(node(1, i, a[1][i]));
q.push(node(n, i, a[n][i]));
}
while(q.size())
{
node tmp = q.top();
q.pop();
for(int i = 0; i < 4; i ++)
{
int xx = tmp.x + d[i][0], yy = tmp.y + d[i][1];
if(vis[xx][yy]) continue;
if(xx > n || xx < 1 || yy > m || yy < 1) continue;
if(a[xx][yy] >= tmp.val)
q.push(node(xx, yy, a[xx][yy]));
else
q.push(node(xx, yy, tmp.val)), res += (tmp.val - a[xx][yy]);
vis[xx][yy] = 1;
}
}
printf("%lld\n", res);
}