牛客OI周赛8-提高组A-用水填坑

题目

链接：

https://ac.nowcoder.com/acm/contest/403/A

来源：牛客网

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

现有一块nm的地，每块11的地的高度为hi,j，在n*m的土地之外的土地高度均为0（即你可以认为最外圈无法积水）

现在下了一场足够大的雨，试求出这块地总共积了多少单位体积的水

输入描述:

第一行两个数 n, m，具体含义见题意
接下来 n 行每行 m 个数, 第 i 行为 hi,1, hi,2, ..., hi,m

输出描述:

输出一行一个数表示积水的总量

示例1

输入

复制

输出

复制

示例2

输入

复制

10 10
0 0 0 0 0 0 0 0 0 0
0 5 2 6 4 3 1 7 8 0
0 6 4 2 3 5 1 4 6 0
0 3 6 4 1 2 4 7 8 0
0 2 5 5 1 2 3 4 4 0
0 2 3 1 5 4 4 1 4 0 
0 4 1 2 3 4 5 2 1 0
0 7 5 5 1 5 4 5 7 0
0 1 3 5 5 4 6 8 7 0
0 0 0 0 0 0 0 0 0 0

输出

复制

备注:

- 对于10%的数据, n, m ≤ 4, h ≤ 5;
- 对于前50%的数据, n, m ≤ 20, h ≤ 10;
- 对于前70%的数据, n, m ≤ 100, h ≤ 50;
- 对于另外10%的数据, 不存在两个连续的块能积水;
- 对于95%的数据, n, m ≤ 500, h ≤ 100.
- 对于100%的数据, n, m ≤ 1000, h ≤ 1000,000,000.

思路

用优先队列bfs，从图中最低的点开始bfs，这样就能从最低的高度开始搜了。

代码

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <sstream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <iomanip>
#include <stack>

using namespace std;

typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 1005;
const int MOD = 1e9 + 9;
const double pi = 3.1415926;

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

struct P
{
    int x, y;
    LL num;
    bool operator < (const P &a) const
    {
        return num > a.num;
    }
};

priority_queue<P> p;
int n, m, vis[1005][1005];
LL mp[N][N], h[N][N];
int dis[][2] = {-1, 0, 1, 0, 0, 1, 0, -1};

int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;++i)
    {
        for(int j = 1;j <= m;++j)
        {
            cin >> mp[i][j];
            if(i == 1 || j == 1 || i == n || j == m)
            {
                vis[i][j] = 1;
                h[i][j] = mp[i][j];
                p.push((P){i, j, mp[i][j]});
            }
        }
    }
    while(!p.empty())
    {
        P now = p.top();
        p.pop();
        for(int i = 0;i < 4;++i)
        {
            int x = now.x + dis[i][0];
            int y = now.y + dis[i][1];
            if(x < 1 || y < 1 || x > n || y > m || vis[x][y])
                continue;
            h[x][y] = max(mp[x][y], now.num);
            vis[x][y] = 1;
            p.push((P){x, y, h[x][y]});
        }
    }
    LL ans = 0;
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= m;++j)
        ans += h[i][j] - mp[i][j];
    cout << ans << endl;
    return 0;
}