The wedding juicer

BFS

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define ll long long
const int N = 300+10;
int mp[N][N],vis[N][N],n,m;
int to[4][2]={-1,0,1,0,0,-1,0,1};         //左右上下
struct nd{
  int x,y,h;
  friend bool operator < (nd a,nd b) {    //重载操作符函数<：队首是最矮的砖块
    return a.h>b.h;                       //比较砖的高度
  }
};
priority_queue<nd> q;                     //定义优先队列

void init(){
  while(!q.empty()) q.pop();              //腾空队列
  nd tp;
  memset(vis,0,sizeof(vis));              //初始化
  for(int i=0;i<n;i++) {
    for(int j=0;j<m;j++) {
      if( i==0 || j==0 || i==n-1 || j==m-1 ) {     //边界
        vis[i][j]=1;                               //标记以访问
        tp.x=i,tp.y=j,tp.h=mp[i][j];               //存上边界的坐标和高度
        q.push(tp);                                //压入队尾
      }
    }
  }
}

void bfs() {
  init();
  ll ans=0;
  nd t,tp;
  while(!q.empty()) {
    tp=q.top();
    q.pop();                              //访问头元素
    for(int i=0;i<4;i++) {                //洪水填充
      int xx=tp.x+to[i][0],yy=tp.y+to[i][1];
      if( 0 <= xx && xx < n && 0 <= yy && yy <m && !vis[xx][yy]) { //不超出边界和没标记上的位置
        vis[xx][yy]=1;                    //标记以访问
        t.x=xx,t.y=yy,t.h=mp[xx][yy];     //存上砖的坐标和高度
        if(t.h<tp.h) ans+=(tp.h-t.h),t.h=tp.h;     //储水容量增加
        q.push(t);                        //压入队尾
      }
    }
  }
  cout<<ans<<endl;
}

int main() {
  while(cin>>m>>n) {                     //读取地图
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
        cin>>mp[i][j];
    bfs();
  }
}

笔记：将砖块看作水桶，决定储水的是最矮的砖块，设定边界并排序是很重要的一环，用“包围法”寻找储水砖块比逐个检查砖块要快很多。