14074: 【原4074】洪水再临

题目

题目描述

author: Vegw 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4074

Description

​ 又是一场热带飓风席卷了圣安东尼奥城，强降水使Oven家的农场饱受摧残。 Oven家农场为一片长度为M,宽度为N的矩形网格区域，每个网格位置(a,b)面积为1，其海拔高度由一个M*N的矩阵表示。 为迎合求生游戏盛行之风，Oven将农场开垦在了视野良好的高地上，其地势高于周边土地，因此农场边界不会积水。 请帮助Oven计算出农场内最大积水体积

Input Format

第一行,两个空格隔开的整数M,N。 (1 <= M,N <= 100) 第2 ~ M+1行输出一个M*N的矩阵。 (0 <= 高度 <= 10000)

Output Format

一行，一个数，表示农场内最大积水体积。

Sample Input

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

Sample Output

3

BugenZhao's solution

//
// Created by BugenZhao on 2019/5/16.
//

//
// Created by BugenZhao on 2019/4/5.
//

#ifndef SBL_BPRIORITYQUEUE_H
#define SBL_BPRIORITYQUEUE_H

namespace bpq {
    template<typename Item>
    struct greater {
        bool operator()(const Item &a, const Item &b) {
            return a > b;
        }
    };

    template<typename Item>
    struct less {
        bool operator()(const Item &a, const Item &b) {
            return a < b;
        }
    };
}

template<typename Item, typename Comparator = bpq::greater<Item>>
class BPriorityQueue {
    Comparator comparator;
    Item *pq;
    int N = 0;
    int maxN;
    int minN;

private:
    bool cmp(int i, int j) {
        return comparator(pq[i], pq[j]);
    }

    void exch(int i, int j) {
        Item item = pq[i];
        pq[i] = pq[j];
        pq[j] = item;
    }

    void resize(int newMaxN) {
        if (newMaxN < minN) {
            if (maxN == minN) return;
            else newMaxN = minN;
        }
        Item *old = pq;
        pq = new Item[newMaxN + 1];
        int length = newMaxN > maxN ? maxN : newMaxN;
        for (int i = 1; i <= length; ++i) {
            pq[i] = old[i];
        }
        delete[] old;
    }

    void swim(int k) {
        while (k > 1 && cmp(k, k / 2)) {
            exch(k / 2, k);
            k /= 2;
        }
    }

    void sink(int k) {
        int j;
        while (2 * k <= N) {
            j = 2 * k;
            j += (j < N && cmp(j + 1, j));
            if (cmp(j, k)) {
                exch(k, j);
                k = j;
            } else break;
        }
    }


public:
    BPriorityQueue() {
        this->maxN = 5;
        this->minN = 5;
        pq = new Item[5 + 1];
    }

    BPriorityQueue(int maxN) {
        this->maxN = maxN;
        this->minN = maxN;
        pq = new Item[maxN + 1];
    }

    BPriorityQueue(const Item *pq, int size) {
        maxN = N = size;
        minN = N;
        this->pq = new Item[size + 1];
        for (int i = 1; i <= N; ++i) {
            this->pq[i] = pq[i - 1];
        }
        for (int k = N / 2; k >= 1; --k) {
            sink(k);
        }
    }

    bool isEmpty() {
        return N == 0;
    }

    int size() {
        return N;
    }

    void insert(const Item &item) {
        if (N == maxN)
            resize(2 * N);
        pq[++N] = item;
        swim(N);
    }

    Item pop() {
        if (N <= maxN / 4)
            resize(maxN / 2);
        Item item = pq[1];
        exch(1, N);
        --N;
        sink(1);
        return item;
    }

    const Item &peek() {
        return pq[1];
    }

    virtual ~BPriorityQueue() {
        delete[] pq;
    }
};


#endif //SBL_BPRIORITYQUEUE_H


#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;

class Point {
public:
    int x, y, h;

    Point(int x = 0, int y = 0, int h = 0) : x(x), y(y), h(h) {}
};

struct cmp {
    bool operator()(const Point &a, const Point &b) {
        return a.h < b.h;
    }
};

int height[100][100];
bool flag[100][100];
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int r, c;
    cin >> r >> c;
    if (r < 3 || c < 3) {
        cout << 0 << endl;
        return 0;
    }
    int ans = 0;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            cin >> height[i][j];
        }
    }

    BPriorityQueue<Point, cmp> pq(r * c);
    for (int i = 0; i < r; ++i) {
        pq.insert(Point(i, 0, height[i][0]));
        flag[i][0] = true;
        pq.insert(Point(i, c - 1, height[i][c - 1]));
        flag[i][c - 1] = true;
    }
    for (int j = 1; j < c - 1; ++j) {
        pq.insert(Point(0, j, height[0][j]));
        flag[0][j] = true;
        pq.insert(Point(r - 1, j, height[r - 1][j]));
        flag[r - 1][j] = true;
    }

    while (!pq.isEmpty()) {
        Point point = pq.pop();
        for (int i = 0; i < 4; ++i) {
            int xx = point.x + dx[i];
            int yy = point.y + dy[i];
            if (xx < 0 || xx >= r || yy < 0 || yy >= c || flag[xx][yy]) continue;
            if (point.h > height[xx][yy]) {
                ans += point.h - height[xx][yy];
                height[xx][yy] = point.h;
            }
            pq.insert(Point(xx, yy, height[xx][yy]));
            flag[xx][yy] = true;
        }
    }

    cout << ans << endl;
    return 0;
}

FineArtz's solution

/* 洪水来袭 */
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

class Point{
public:
    int x = 0, y = 0;
};

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int m, n;
int a[105][105];
bool b[105][105];
bool v[105][105];
long long ans = 0;

bool check(const int &x, const int &y){
    return (x >= 0 && y >= 0 && x <= m + 1 && y <= n + 1);
}

void ff(int x, int y){
    Point st;
    st.x = x;
    st.y = y;
    queue<Point> q;
    q.push(st);
    Point now, next;
    while (!q.empty()){
        now = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k){
            next.x = now.x + dx[k];
            next.y = now.y + dy[k];
            if (check(next.x, next.y)){
                if (!b[next.x][next.y] && a[now.x][now.y] <= a[next.x][next.y]){
                    b[next.x][next.y] = true;
                    q.push(next);
                }
            }
        }
    }
}

bool checkw(int x, int y){
    Point st;
    st.x = x;
    st.y = y;
    bool vis[105][105];
    memset(vis, 0, sizeof(vis));
    queue<Point> q;
    q.push(st);
    v[st.x][st.y] = true;
    Point now, next;
    while (!q.empty()){
        now = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k){
            next.x = now.x + dx[k];
            next.y = now.y + dy[k];
            if (check(next.x, next.y) && !vis[next.x][next.y]){
                if (a[next.x][next.y] < a[now.x][now.y]) return false;
                if (a[next.x][next.y] == a[now.x][now.y]){
                    if (b[next.x][next.y]) return false;
                    vis[next.x][next.y] = true;
                    q.push(next);
                }
            }
        }
    }
    return true;
}
bool fill(){
    for (int i = 2; i <= m - 1; ++i)
        for (int j = 2; j <= n - 1; ++j)
            if (!b[i][j]) return false;
    return true;
}

int main(){
    cin >> m >> n;
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> a[i][j];
    memset(b, 0, sizeof(b));
    ff(0, 0);
    for (int water = 1; water <= 10000; ++water){
        for (int i = 2; i <= m - 1; ++i)
            for (int j = 2; j <= n - 1; ++j)
                if (!b[i][j] && water > a[i][j]){
                    ++ans;
                    ++a[i][j];
                    for (int k = 0; k < 4; ++k){
                        int xx = i + dx[k];
                        int yy = j + dy[k];
                        if (a[xx][yy] <= a[i][j] && b[xx][yy]){
                            ff(xx, yy);
                            break;
                        }
                    }
                }
        if (fill()) break;
    }
    cout << ans << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstring"
#include "cstdio"
#include "cmath"
using namespace std;

int mmin(int a, int b) {
    return a < b ? a : b;
}

int mmin(int a, int b, int c, int d) {
    return mmin(mmin(a, b), mmin(c, d));
}

int map_data[109][109] = { 0 };
int water[109][109] = { 0 };

int main() {
    int m, n;
    scanf("%d %d", &m, &n);

    int max_height = 0;

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &map_data[i][j]);
            max_height = map_data[i][j] > max_height ? map_data[i][j] : max_height;
        }
    }

    //装水
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            water[i][j] = max_height - map_data[i][j];
        }
    }

    //漏水
    for (int leak = 0;;) {
        leak = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                auto cur_min = mmin(map_data[i - 1][j] + water[i - 1][j], map_data[i][j - 1] + water[i][j - 1],
                    map_data[i + 1][j] + water[i + 1][j], map_data[i][j + 1] + water[i][j + 1]);
                if (water[i][j] > 0 && cur_min < map_data[i][j] + water[i][j]) {
                    if (map_data[i][j] >= cur_min) {
                        leak += water[i][j];
                        water[i][j] = 0;
                    }
                    else {
                        leak += map_data[i][j] + water[i][j] - cur_min;
                        water[i][j] = cur_min - map_data[i][j];
                    }
                }
            }
        }
        if (leak == 0)
            break;
    }

    //统计
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            ans += water[i][j];
        }
    }

    cout << ans;

    return 0;
}

skyzh's solution

#include <iostream>
#include <cstdio>
#include <climits>

using namespace std;

int M, N;
int MAP[100][100];

template<typename T>
struct Heap {
    T *x;
    int N;

    Heap(int cap = 10000) : N(0) { x = new T[cap + 1]; }

    ~Heap() { delete[] x; }

    void swim(int i) {
        while (i > 1 && x[i] < x[i / 2]) {
            swap(x[i], x[i / 2]);
            i /= 2;
        }
    }

    void sink(int i) {
        while (i * 2 <= N) {
            int j = i * 2;
            if (j < N && x[j + 1] < x[j]) ++j;
            if (x[j] < x[i]) {
                swap(x[j], x[i]);
                i = j;
            } else break;
        }
    }

    void push(const T &d) {
        x[++N] = d;
        swim(N);
    }

    void pop() {
        swap(x[1], x[N--]);
        sink(1);
    }

    T &top() {
        return x[1];
    }
};

struct Pair {
    int v;
    int x, y;

    friend bool operator<(const Pair &a, const Pair &b) {
        return a.v < b.v;
    }

    Pair(int v, int x, int y) : v(v), x(x), y(y) {}
    Pair() {}
};

bool visited[100][100] = {0};
Heap<Pair> h(10000);
int ans = 0;
int pop_max = INT_MIN;

int main() {
    scanf("%d%d", &M, &N);
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &MAP[i][j]);
        }
    }
    int cnt = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (i == 0 || i == M - 1 || j == 0 || j == N - 1) {
                visited[i][j] = true;
                h.push(Pair(MAP[i][j], i, j));
                ++cnt;
            }
        }
    }
    while (cnt < N * M) {
        Pair t = h.top();
        h.pop();
        pop_max = max(pop_max, t.v);
        static int direction[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
        for (int d = 0; d < 4; d++) {
            int _x = t.x + direction[d][0];
            int _y = t.y + direction[d][1];
            if (_x >= 0 && _y >= 0 && _x < M && _y < N) {
                if (!visited[_x][_y]) {
                    visited[_x][_y] = true;
                    ++cnt;
                    if (MAP[_x][_y] < pop_max) {
                        ans += pop_max - MAP[_x][_y];
                    }
                    h.push(Pair(MAP[_x][_y], _x, _y));
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}