题目链接:http://nyoj.top/problem/547

  • 内存限制:64MB 时间限制:1000ms

题目描述

Dr.Kong has taken a side job designing interesting punch-bowl designs. The designs are created as follows:
  * A flat board of size W cm *  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!

Dr.Kong 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.

输入描述

  * 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.

输出描述

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

样例输入

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

样例输出

12

解题思路

题意:就是有一个N*M的“碗“，数字对应位置有一个高度的柱子，然后如果往里面无限加水，问最多会存下多少水。
思路:一个位置能存下多少水是由四周最低的柱子高度决定的，所以我们先把碗的边缘的位置的高度存起来，然后找出最低的，每次都从最低的边界向内部注水(仅与边界相邻的内部)，推出四周四个位置的水高度，如果发现高度比本位置低的就说明此位置最高的水位就是本位置的高度，比本位置高的说明存不下水。然后把注水后的柱子当作新的边界，也就是把边界放到一个优先队列中，每次都让高度最小的边界出队(优先队列)。

#include <bits/stdc++.h>
const int MAXN = 305;
using namespace std;
struct edge {
    int x, y, h;
    friend bool operator < (edge a, edge b) {
        return a.h > b.h;
    }
}u;
int n, m, vis[MAXN][MAXN], mp[MAXN][MAXN];
int arr[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool Judge(int x, int y) {
    if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y])
        return true;
    return false;
}
priority_queue <edge> Q;
int main() {
    long long ans;
    while (~scanf("%d%d", &m, &n)) {
        ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                vis[i][j] = 0;
                scanf("%d", &mp[i][j]);
                if (!i || !j || i == n - 1  || j == m - 1) {
                    vis[i][j] = 1;
                    Q.push((edge){i, j, mp[i][j]});
                }
            }
        }
        while (!Q.empty()) {
            u = Q.top();
            Q.pop();
            for (int i = 0; i < 4; i++) {
                int tx = u.x + arr[i][0];
                int ty = u.y + arr[i][1];
                if (Judge(tx, ty)) {
                    vis[tx][ty] = 1;
                    if (u.h > mp[tx][ty]) {
                        ans += 1ll * (u.h - mp[tx][ty]);
                        mp[tx][ty] = u.h;
                    }
                    Q.push((edge){tx, ty, mp[tx][ty]});
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}