蒟蒻很菜, 题解也写不好, 善良的年轻人给个赞吧 QWQ ❤️
问题陈述
有一座大小为 $H \times W$ 的岛屿,四面环海。
岛被分为 $H$ 行和 $W$ 列的 $1 \times 1$ 部分,从上数第 $i$ 行和从左数第 $j$ 列处的剖面高程(相对于当前水位l)是 $A_{i,j}$ 。
从现在开始,海平面每年上升 $1$ 。
这里,垂直或水平与海相邻的部分或沉入海中的部分,其高程不超过海堤艾尔会沉入大海。
在这里,当一段新沉入海中时,任何高度不超过海平面的垂直或水平相邻部分也将同时沉入海中,并且对于新下沉的部分重复该过程。对于每个 $i=1,2,\ldots, Y$ ,请找出从现在起 $i$ 年后仍高于海平面的岛屿面积。
约束
-
$1 \leq H, W \leq 1000$
-
$1 \leq Y \leq 10^5$
-
$1 \leq A_{i,j} \leq 10^5$
-所有输入值均为整数。
输入
输入来自标准输入,格式如下:
$H$ $W$ $Y$
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\ldots$ $A_{H,W}$
样本输入1
3 3 5
10 2 10
3 1 4
10 5 10
示例输出1
9
7
6
5
4
设 $(i,j)$ 表示从上往下第 $i$ 行和从左往下第 $j$ 列的部分。
然后,发生以下情况:
- $1$ 年后,海平面比现在高 $1$ ,
但没有标高为 $1$ 的断面临海,因此没有断面下沉。因此,第一行应包含 $9$ 。- $2$ 年后,海平面比现在高 $2$ , $(1,2)$ 沉入海中。
这使得 $(2,2)$ 邻近一个凹陷段,其高程不大于 $2$ ,因此也会下沉。在这一点上没有其他部分下沉。因此,两个部分下沉,第二行应包含 $9-2=7$ 。- $3$ 年后,海平面比现在高 $3$ , $(2,1)$ 沉入海中。没有其他部分下沉。
因此,第三行应包含 $6$ 。- $4$ 年后,海平面比现在高 $4$ , $(2,3)$ 沉入海中。没有其他部分下沉。
因此,第四行应包含 $5$ 。- $5$ 年后,海平面比现在高 $5$ , $(3,2)$ 沉入海中。没有其他部分下沉。
因此,第五行应包含 $4$ 。因此,请按此顺序分别打印 $9$ 、 $7$ 、 $6$ 、 $5$ 和 $4$ ,并分别在新行上打印。
。
简单来说题目就是这样的
给你你个网格
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\ldots$ $A_{H,W}$
其中$A_{i,j}$ 表示第i座山的高度
此时有洪水降临, 洪水的高度最多为Y
随着时间的变化洪水从1一直涨到Y
请问洪水高度从1~Y时每次有多少岛屿没被淹(当一个岛屿的高度≤洪水的高度, 此时我们定义这个岛屿被淹了)
暴力解法 $O(H•W•Y)$
我们可以这样思考,枚举洪水的高度
在每次循环中枚举整个网格 写一个floodFill(洪水填充)
其中每次查找当前网格是否被淹 然后扩展
很简单的思路 然后 TLE 了
正解 $O(max(H, W) • Y)$
可以有一个这样的想法 按照洪水每次的入侵 一层一层的往里拓展
就像这样
但每次填充的时候, 会有洪水流进,会导致其他的山被淹没
但如果我们又写了一个dfs去查询时间复杂度又回到了之前的暴力算法
难道真的没办法了吗?!?!
有别忘了前面的floodFill里面最重要的性质就是继承啊
我们可以刚开始预选最外面一圈的山, 然后每次随着洪水高度的增加 每次bfs
这个时候问题有出现了, bfs会死循环需要判读当前队列里最小的高度值是否会≤洪水的高度
直接枚举太慢了, 这个时候就可以用小根堆(priority_queue)
它可以以O(1)的时间查找当前序列里最小的值
这样就可以直接在while上面加上heap.top().h≤i
然后就会输出一个远比样例结果小的值
为什么? 因为我们每次都会只会扩展一步
这个时候就会出现一个奇怪的组合dfs嵌套bfs(个人第一次用)
我们只需要把dfs和bfs联合起来, bfs的扩展用dfs, dfs和bfs共用一个标记数组
此时思路完结
请不要直接抄代码, 不如你会道心全毁, 此生无法搞竞赛
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
struct Cow
{
int x, y, h;
bool operator> (const Cow &u) const
{
return u.h < h;
}
// 注意这里的重载 > 对应着greater 改成 < 会编译错误
};
const int N = 1010;
int w[N][N]; // 山(岛屿)的高度
bool st[N][N]; // 标记数组
priority_queue<Cow, vector<Cow>, greater<Cow>> heap;
int n, m;
int cnt; //没被淹山(岛屿)的数量
void dfs(int x, int y, int k) // x和y存储的是坐标, k是当前洪水的高度
{
st[x][y] = true;// 标记
cnt--;// 代表一个山(岛屿)被淹了
for (int i = 0; i < 4; i++)
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b]) // 当前节点合法
{
heap.push({a, b, w[a][b]});// 将当前节点推入堆中 跟下面dfs判断放在一起会WA 我们的bfs是要推展每一个节点的
if (w[a][b] <= k) dfs(a, b, k); // 当前山(岛屿)会被淹
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int k;
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) cin >> w[i][j];
for (int i = 0; i < m; i++) heap.push({0, i, w[0][i]});
for (int i = 1; i < n; i++) heap.push({i, 0, w[i][0]});
for (int i = 1; i < m; i++) heap.push({n - 1, i, w[n - 1][i]});
for (int i = 1; i < n - 1; i++) heap.push({i, m - 1, w[i][m - 1]});
// 最外面的一层网格
// ***********
// * *
// * *
// * *
// ***********
cnt = n * m; // 刚开始有n*m个山(岛屿)
for (int i = 1; i <= k; i++)
{
while (heap.size() && heap.top().h <= i) // 当前堆最小的高度的山(岛屿)会被淹
{
Cow t = heap.top();
heap.pop();
if (!st[t.x][t.y] && t.h <= i) dfs(t.x, t.y, i); // 每次拓展dfs
}
cout << cnt << '\n';
}
return 0;
}