题目描述
有一块矩形土地被划分成 n*m 个正方形小块。这些小块高低不平，每一小块都有自己的高度。水流可以由任意一块地流向周围四个方向的四块地中，但是不能直接流入对角相连的小块中。一场大雨后，由于地势高低不同，许多地方都积存了不少降水。给定每个小块的高度，求每个小块的积水高度。注意：假设矩形地外围无限大且高度为 0。
输入数据
第一行包含两个非负整数 n,m。接下来 n 行每行 m 个整数表示第 i 行第 j 列的小块的高度。
输出数据
输出 n 行，每行 m 个由空格隔开的非负整数，表示每个小块的积水高度。
样例输入
3 3
4 4 0
2 1 3
3 3 -1
样例输出
0 0 0
0 1 0
0 0 1
数据范围
对于 20%的数据 n,m<=4
对于 40%的数据 n,m<=15
对于 60%的数据 n,m<=50
对于 100%的数据 n,m<=300，|小块高度|<=10^9。
在每一部分数据中，均有一半数据保证小块高度非负
1. 考虑每处的积水是从哪流出去的。
2. 那么反过来做，考虑当前位置是哪些地方的出口。
3. 由于水往低处流，所以当然要先考虑低处，于是用小根堆维护。
4. 先将最外围全部入队。向其他点扩展，如果扩展点的高度低于
当前点，那么对其累加答案；否则如果扩展点的高度高于当前
点，则扩展点不会积水。更新完扩展点后，将其入队，其高度
取当前点与扩展点的最大值。
5. 需要明确的一点是我们每次都是从最低点出发的，即每个点一
定是被主要限制其高度的一个方向的节点更新的。
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int nx[4]={-1,1,0,0}; 5 const int ny[4]={0,0,-1,1}; 6 int n,m,tx,ty; 7 bool vis[350][350]; 8 int a[350][350],ans[350][350]; 9 struct node 10 { 11 int x,y,val; 12 bool operator<(const node & p)const 13 { 14 return val>p.val; 15 } 16 }tmp; 17 priority_queue<node > q; 18 bool check(int x,int y) 19 { 20 return x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y]; 21 } 22 void bfs() 23 { 24 while(!q.empty()) 25 { 26 tmp=q.top(); 27 q.pop(); 28 for(int i=0;i<=3;++i) 29 { 30 tx=tmp.x+nx[i]; 31 ty=tmp.y+ny[i]; 32 if(!check(tx,ty)) 33 continue; 34 if(a[tx][ty]<tmp.val) 35 ans[tx][ty]=tmp.val-a[tx][ty]; 36 vis[tx][ty]=true; 37 q.push(node{tx,ty,max(a[tx][ty],tmp.val)}); 38 } 39 } 40 } 41 int main() 42 { 43 scanf("%d%d",&n,&m); 44 for(int i=1;i<=n;++i) 45 for(int j=1;j<=m;++j) 46 scanf("%d",&a[i][j]); 47 for(int i=1;i<=n;++i) 48 { 49 q.push(node{0,i,0}); 50 q.push(node{n+1,i,0}); 51 } 52 for(int i=0;i<=m+1;++i) 53 { 54 q.push(node{i,0,0}); 55 q.push(node{i,m+1,0}); 56 } 57 bfs(); 58 for(int i=1;i<=n;++i) 59 { 60 for(int j=1;j<=m;++j) 61 printf("%d ",ans[i][j]); 62 printf(" "); 63 } 64 return 0; 65 }