自动搬运

查看原文

来自洛谷，原作者为

	☆木辛土申☆ 我要变强啊~~

搬运于2025-08-24 22:17:02，当前版本为作者最后更新于2020-02-13 17:31:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里先讲一下FloodFill算法

(已了解的请自行跳过）

FloodFill算法就是一种用指定的颜色填充某个密闭区域的算法，一种分割图像的基本算法，就相当于于画图中的油漆桶，一倒泼一片的那种，可以用来单纯的“填颜色”，或者求连通块。我通常用BFS算法实现，当然也可以用DFS，看个人喜好啦。 P.S这里推荐一个讲的比较好的博客--->泛洪算法.

现在看两道道例题啦

• P1162 填涂颜色
• P1506 拯救oibh总部

这两道题目都是基础的填色题，我们考虑向外面泼一格水，让水它自由的流，遇到障碍就停止，此时没有被水覆盖到的部分便是我们要求的答案。

但是我们现在有一个问题，那格水该怎么泼呢？

这里提供两种方法：

• 1.在读入数据的过程中特判边界点存入队列，这里以P1506为例：

for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		read(map[i][j]);
		if((i==1||j==1||i==n||j==m)&&map[i][j]=='0'){
			q.push(std::make_pair(i,j));
			vis[i][j]=true;
		}
	}
}//map是数组，不是std::map，个人不太喜欢使用万能头

• 2.拓宽边界，建立虚拟边界，将水泼在边界外与虚拟边界之间的一点，这里将越界条件改一下(需要数组从1开始存信息)：

bool illegal(int x,int y){
	return x<1||x>n||y<1||y>n||vis[x][y];
}//这是原来的条件
bool illegal(int x,int y){
	return x<0||x>n+1||y<0||y>m+1||vis[x][y];
}//这是更改后的条件

这样使用时可直接调用bfs(0,0)或dfs(0,0)而不用特判边界点了。

边界特判处理完后，代码就很容易实现了。这里给出一种普遍实现：

//方向常量数组
const int fx[]={};
const int fy[]={};
//这里{}内枚举可能的方向

struct Node{
//定义节点信息，如坐标信息
//定义构造函数（可选）
//定义比较函数（如本题）
}

//定义越界判断函数
bool illegal(int x,int y);

//定义队列

//搜索函数
bfs(int x,int y){
	while(队列不为空){
    	取出队首节点;
        	for()扩展节点并判断;
        		更新信息;
        		如果符合条件加入队列;
    }
}
	

int main(){
	bfs();
    输出答案;
    return 0;//一定别忘了
}

关于本题

本题本质上也是一个FloodFill，但实现上有略微不同。

仔细阅读，题意很简单，一个矩阵上的所有点上都有一个立方体柱，求这些立方体柱构成的容器最多能盛装多少液体。

首先我们可以想到一种朴素做法：

对每一个高度的平面进行一次FloodFill，但这样做时间复杂度太高，高度在10^9级别，再乘上平面单次FloodFill的O（n^2）n_max=300，显然tle了。

既然有了思路还可以改一下啦

我们对高度进行离散化，离散化后的水平面最多有300*300=90000个，每个平面进行一次FloodFill，加上离散化查找的复杂度，虽比第一种方法优秀许多，但仍然是妥妥的tle（实测能得53分，数据真是太水了。。。。（bushi））

接下来是正解啦（我先放代码了）

我想了好久才想出正解，我真是太蒻了。。（认真.jpg）

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>

typedef long long LL;
const int SIZE=301;
const int fx[]={0,0,0,1,-1};
const int fy[]={0,1,-1,0,0}; 
int map[SIZE][SIZE],h,w;
bool vis[SIZE][SIZE];

struct Node {
	int x,y,z;//x是行，y是列，z是高度 
	Node(const int &key1,const int &key2,const int &key3):x(key1),y(key2),z(key3) {}
	inline bool operator <(const Node &in)const {
		return in.z<this->z;
	}
};

template<typename T>inline void read(T &res){
	res=0;char ch=getchar();bool neg=false;
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') neg=true;
	for(; isdigit(ch);ch=getchar()) res=(res<<1)+(res<<3)+(ch^48);
	if(neg) res=-res;
}

inline bool illegal(int x,int y){
	return x<1||x>h||y<1||y>w||vis[x][y];
}

std::priority_queue<Node> q;

inline void init(int w,int h){
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			read(map[i][j]);
			if(i==1||j==1||i==h||j==w){
				q.push(Node(i,j,map[i][j]));
				vis[i][j]=true;
			}
		}
	}
}

inline LL floodfill(){
	LL res=0;
	while(!q.empty()){
		int x=q.top().x;
		int y=q.top().y;
		int h=q.top().z;
		q.pop();
		for(int i=1;i<=4;i++){
			int xx=x+fx[i];
			int yy=y+fy[i];
			if(illegal(xx,yy)) continue;
			if(map[xx][yy]<h) res+=h-map[xx][yy],map[xx][yy]=h;
			q.push(Node(xx,yy,map[xx][yy]));
			vis[xx][yy]=true;
		}
	}
	return res;
}

signed main() {
	read(w),read(h),init(w,h);
	printf("%lld\n",floodfill());
	return 0;
}

代码相信大家看后都很好理解的，可为什么这样是对的呢。

这个问题的重点是计算顺序。如果我们每次选择边界上最低的点开始FloodFill则果汁一定不会洒出去，比它低的点显然可以盛到液体，而高的点会成为新的边界，于是我们用一个优先队列来维护，每次取高度最低的点进行扩展，就可以了。

在这里感谢这篇博客USACO 05Gold给予了我思路，上面的思路十分直接，我真是太蒻了（强调）。

相信之后一定会有写的比我好的多的题解，如果通过的话，这就是我的第一篇题解了。

另外，欢迎大家来扩列啊(^▽^)。