「雅礼day2」水流water - Bfs

题目大意

有一块矩形土地被划分成 n*m 个正方形小块。这些小块高低不平，每一小块都有自己的高度。水流可以由任意一块地流向周围四个方向的四块地中，但是不能直接流入对角相连的小块中。
一场大雨后，由于地势高低不同，许多地方都积存了不少降水。给定每个小块的高度，求每个小块的积水高度。
注意：假设矩形地外围无限大且高度为 0。

---

题目分析

一块区域能够积水的条件是其外围全部比这块区域高，那么这块区域可以积水的高度就是外围的最小值减去当前地面高度。

从内向外不好考虑，我们从外向内考虑，统计一个外围的点对内部的贡献。
设$dist[x,y]$表示在$(x,y)$外围的点中最大值的最小值。
那么显然对$(x,y)$做出贡献的点便是这些最小值的点，因此我们用一个小根堆维护状态，每次取出$dist$最小的点。
每次扩展的时候，若扩展的点比当前点高，那么说明这个路径无法继续做出贡献了，将扩展的点入堆，$dist$记为扩展点高度。
若扩展的点比当前点低，说明扩展的点肯定无用。（因为外围有一个更高的点）将$dist$记为当前状态的$dist$。

然后用$Bfs$更新每个点的$dist$即可。

实现类似求最小生成树的Prim算法。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=305,Dirx[]= {0,1,-1,0,0},Diry[]= {0,0,0,1,-1};
int n,m,a[maxn][maxn],dist[maxn][maxn],vst[maxn][maxn];
struct HeapNode {
	int x,y,d;
	bool operator < (const HeapNode& b) const {
		return d>b.d;
	}
};
void Bfs() {
	memset(dist,0x3f,sizeof(dist));
	priority_queue<HeapNode>Q;
	for(int i=1; i<=n; i++) {
		dist[i][0]=dist[i][m+1]=0;
		Q.push((HeapNode) {i,0,0});
		Q.push((HeapNode) {i,m+1,0});
	}
	for(int i=1; i<=m; i++) {
		dist[0][i]=dist[n+1][i]=0;
		Q.push((HeapNode) {0,i,0});
		Q.push((HeapNode) {n+1,i,0});
	}
	while(!Q.empty()) {
		HeapNode Now=Q.top();
		Q.pop();
		if(vst[Now.x][Now.y])continue;
		vst[Now.x][Now.y]=1;
		for(int k=1; k<=4; k++) {
			HeapNode Next= {Now.x+Dirx[k],Now.y+Diry[k],max(Now.d,a[Next.x][Next.y])};
			if(vst[Next.x][Next.y]||Next.x<1||Next.x>n||Next.y<1||Next.y>m)continue;
			if(dist[Next.x][Next.y]>Next.d) {
				dist[Next.x][Next.y]=Next.d;
				Q.push(Next);
			}
		}
	}
}
int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			a[i][j]=Get_Int();
	Bfs();
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++)printf("%d ",dist[i][j]-a[i][j]);
		putchar('\n');
	}
	return 0;
}