题解 - P5930

· · 题解

P5930 降水 の 题目传送门。

题目简化

给定一块区域 a_{n, m}，每块土地都有一个高度。
下雨了。

求其共装了多少水。

思路讲解

稍微观察，可以发现，只有本身与外界隔离时，才会积住水。
那么是不是可以从外界向里看？
自然，最外面一圈是积不住水的，所以从最外圈开始向内泄水。
考虑搜索。

代码实现

考虑 dfs 或 bfs。

dfs

在看到这题的第一眼，我就想写 dfs，为什么？简单啊。
先将四周存入一个数组 r，再挨个 dfs。

CODE

void dfs (clod t) {
    for (int i = -1; i <= 1; ++ i) for (int j = -1; j <= 1; ++ j) {
        int px = t.x+i, py = t.y+j;
        if (abs(i+j)==1 && px>1 && py>1 && px<n && py<m && w[px][py] > w[t.x][t.y]) {
            if(w[t.x][t.y] > h[px][py]) w[px][py] = w[t.x][t.y];
            if(w[t.x][t.y] <= h[px][py]) w[px][py] = h[px][py];
            v[px][py] = 1;
            dfs({px, py, w[px][py]});
        }
    }
    return ;
}

弄出来后，感觉太慢了，n 和 m 如果再大一点就寄了，我们要有危机意识，所以考虑优化：加入 v_{n, m}，判断是否遍历过。
弄完之后发现：每块土不一定只从一个方向泄水，于是寄了。

怎么办呢？我们还是得有危机意识，考虑 bfs。

dfs

还是先将四周存入队列 q，再进行 bfs。

CODE

void bfs () {
    while (!q.empty()) {
        clod t = q.top();
        q.pop();
        for (int i = -1; i <= 1; ++ i) for (int j = -1; j <= 1; ++ j) {
            int px = t.x+i, py = t.y+j;
            if (abs(i+j)==1 && px>1 && py>1 && px<n && py<m && w[px][py] > w[t.x][t.y]) {
                if(w[t.x][t.y] > h[px][py]) w[px][py] = w[t.x][t.y];
                if(w[t.x][t.y] <= h[px][py]) w[px][py] = h[px][py];
                q.push({px, py, w[px][py]});
            }
        }
    }
    return ;
}
int main () {

    ...
}

啊！神清气爽！虽然还是被最优解碾压，但也才0.1s，稳过了就。

E.N.D.