C++问题：积木问题
【题目描述】
皮皮喜欢玩各种各样的积木，他有一个n行m列的棋盘，棋盘的每一格都是正方形，皮皮用很多正方体积木在棋盘上搭建了一个“城堡”，其中皮皮在棋盘第i行第j列的格子中放了a
i,j
个方块，因此这一格的高度为a
i,j
。
昨晚下了一场小雨，皮皮忘记把积木收回来，因此棋盘中出现了一些积水，具体来说，如果一个区域周围的高度比区域内部更高，水就无法流出来，就会残留在棋盘上。
如果皮皮的棋盘中每个格子的高度（指积木数量）如左图所示，那么棋盘的积水深度如右图：
(图像: image.png)
图中蓝色部分为积水面积，颜色代表积水的深度，整个棋盘共积水16个单位（一个正方体积木的体积看做一个单位）。
给定皮皮搭建的“城堡”，请找出所有可能积水的地方（图中蓝色部分），统计它们积水的体积总和（换算成正方体积木的体积）。
【输入格式】
输入第1行，两个整数n和m，表示棋盘的行列。
第2到n+1行，每行m个非负整数，表示对应格子上放的积木数量。
【输出格式】
一个数字，表示积水的总体积。
【输入输出样例#1】
输入#1
5 5
5 3 4 3 4
4 0 1 0 5
1 4 2 0 3
5 1 3 0 4
0 2 5 3 5
复制
输出#1
16
复制
【输入输出样例#2】
输入#2
4 5
1 1 1 1 1
1 0 1 0 0
1 0 1 0 1
1 1 1 1 1
复制
输出#2
2
复制
【输入输出样例#3】
输入#3
12 10
6 1 1 1 5 1 1 3 7 3
4 1 4 3 4 3 7 5 5 5
2 4 1 1 1 7 0 7 7 5
1 3 2 3 0 5 1 0 7 0
3 4 4 3 3 7 3 7 2 0
3 5 3 3 0 1 5 0 5 8
1 4 0 3 1 0 5 1 0 5
3 0 5 3 2 2 5 6 1 5
5 2 5 2 5 5 2 0 1 5
4 1 5 1 3 1 6 2 3 5
4 5 5 5 5 5 5 5 5 5
5 3 2 1 1 5 0 0 1 0
复制
输出#3
87
复制
【数据范围】
对于20%的数据，1≤n,m≤10，0≤a
i,j
≤1。
对于40%的数据，1≤n,m≤50。
另有10%的数据，保证除了第一行、最后一行、第一列、最后一列外，所有a
i,j
均为0。
对于100%的数据，1≤n,m≤500，1≤a
i,j
≤10
9
。
其实就是一个广度优先搜索问题
【思路】
首先，从棋盘的四周开始，将所有高度为0的格子加入队列，然后进行BFS搜索，每次取出队首元素，将其四周未访问过且高度小于等于当前高度的格子加入队列，并更新积水高度。最后，遍历整个棋盘，累加每个格子的积水高度即可得到答案
【运行截图】
【代码】
#include <iostream>
#include <queue>
using namespace std;
const int N = 1010;
int n, m;
int h[N][N];
bool st[N][N];
int water[N][N];
struct node {
int x, y, h;
bool operator< (const node &t) const {
return h > t.h;
}
};
priority_queue<node> heap;
int bfs() {
int res = 0;
while (heap.size()) {
auto t = heap.top();
heap.pop();
int x = t.x, y = t.y;
if (st[x][y]) continue;
st[x][y] = true;
res += water[x][y];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
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) continue;
if (st[a][b]) continue;
if (h[a][b] < t.h) {
water[a][b] = t.h - h[a][b];
heap.push({a, b, t.h});
} else {
heap.push({a, b, h[a][b]});
}
}
}
return res;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> h[i][j];
if (i == 1 || i == n || j == 1 || j == m) heap.push({i, j, h[i][j]});
}
cout << bfs() << endl;
return 0;
}
思路，首先假设全部都是积水
然后遍历数组，对应每个元素，判断其多少积水可以排除
遍历之后的就是结果
我的思路是每一格按照上左右下的顺序跑一边，将周围小于该点的值记录下来，然后取一个最大值，如果最大值小于该点的值那就说明水会降到当前格子内，并且有(ai,j-max)的体积，用flag标注该处是否有水流入，最后统计flag为1的所有(a[i][j]-max)的值之和即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 510;//数组大小
int n,m,ans;//ans记录答案
int a[N][N],st[N][N];//st记录当前格最高高度
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
//dx[] dy[]记录四联通情况
void dfs(int ida,int idb)
{
int hi=a[ida][idb];
for(int i=0;i<4;i++)
{
int nx=ida+dx[i],ny=idb+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&st[nx][ny]+1<st[ida][idb])
hi=min(hi,st[ida][idb]-st[nx][ny]-1);//更新当前最高高度
}
if(hi-a[ida][idb]>0&&!st[ida][idb])
{
ans+=(hi-a[ida][idb]);
st[ida][idb]=hi;//标记有水流入，并记录最大值。
}
for(int i=0;i<4;i++)
{
int nx=ida+dx[i],ny=idb+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&st[nx][ny]+1<st[ida][idb])
dfs(nx,ny);//递归遍历
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(j==1||j==m||i==1||i==n) st[i][j]=-1;//便于dfs遍历出界
else st[i][j]=0;//未被水覆盖
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(st[i][j]==0) dfs(i,j);
cout<<ans<<endl;
return 0;
}
对于这个问题，我认为对于每个格子，我们需要统计四周最高的高度，然后判断当前高度是否小于这个最高高度，如果是则表示这个格子有积水。这个过程可以通过预处理前缀和来优化，使得每次询问的时间复杂度变为常数级别。
时间复杂度
预处理前缀和需要 O(n 2) 的时间复杂度，然后对于每个格子只需要常数级别的时间复杂度即可，所以总时间复杂度是 O(n 2)。代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
int h[MAXN][MAXN]; // 存储高度
int l[MAXN][MAXN]; // 存储左边最高的高度
int r[MAXN][MAXN]; // 存储右边最高的高度
int u[MAXN][MAXN]; // 存储上边最高的高度
int d[MAXN][MAXN]; // 存储下边最高的高度
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> h[i][j];
}
}
// 预处理前缀和
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
l[i][j] = max(l[i][j-1], h[i][j]);
u[i][j] = max(u[i-1][j], h[i][j]);
}
}
for (int i = n; i >= 1; i--) {
for (int j = m; j >= 1; j--) {
r[i][j] = max(r[i][j+1], h[i][j]);
d[i][j] = max(d[i+1][j], h[i][j]);
}
}
// 统计积水总体积
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int height = min(min(l[i][j], r[i][j]), min(u[i][j], d[i][j]));
if (height > h[i][j]) {
ans += height - h[i][j];
}
}
}
cout << ans << endl;
return 0;
}
其中，l[i][j]、r[i][j]、u[i][j]、d[i][j] 分别表示第 i 行第 j 列格子左边、右边、上边、下边最高的高度。预处理前缀和的过程中，我们可以利用动态规划的思想，从左到右、从上到下依次求解。接着，我们遍历每个格子，统计积水总体积。如果当前格子高度小于四周最高高度中的最小值，则表示当前格子有积水，将积水体积加入答案中。
bfs和dfs遍历
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, M = N * N;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
int n, m;
int h[N][N], e[M], ne[M], idx;
int q[M];
bool st[N][N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a][0], h[a][0] = idx++;
}
void bfs(int x, int y) {
int hh = 0, tt = 0;
q[0] = x * N + y;
st[x][y] = true;
while (hh <= tt) {
int t = q[hh++];
int x = t / N, y = t % N;
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) continue;
if (st[a][b]) continue;
if (h[a][b] < h[x][y]) {
q[++tt] = a * N + b;
st[a][b] = true;
} else {
add(t, a * N + b);
}
}
}
}
int dfs(int u, int& minh) {
int res = 1;
int x = u / N, y = u % N;
minh = min(minh, h[x][y]);
for (int i = h[x][1]; ~i; i = ne[i]) {
int j = e[i];
int a = j / N, b = j % N;
int t = 0;
if (h[a][b] == h[x][y] - 1) {
res += dfs(j, t);
}
}
return res;
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> h[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (h[i][j] && !st[i][j]) {
bfs(i, j);
}
}
}
int res = 0;
for (int i = 0; i < n * m; i++) {
int x = i / N, y = i % N;
int minh = h[x][y];
if (h[x][y] && !st[x][y]) {
res += dfs(i, minh) * (minh - h[x][y]);
}
}
cout << res << endl;
return 0;
}