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计算出农场内最大积水体积

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;
}
``````