题解 P6063 【[USACO05JAN]The Wedding Juicer G】
这里先讲一下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给予了我思路，上面的思路十分直接，我真是太蒻了（强调）。
相信之后一定会有写的比我好的多的题解，如果通过的话，这就是我的第一篇题解了。
另外，欢迎大家来扩列啊(^▽^)。