网站建设项目需求分析,网站建设代理推广徽信xiala5效果好,dedecms 迁移 wordpress,服装品牌网页设计图片采取从外层边界#xff0c;一步一步向内部拓展的策略#xff0c;具体来说#xff0c;一开始将最外面一层的点加入队列#xff0c;并标记这些点的坐标已经被访问
取出队列中高度最低的点#xff0c;将其弹出#xff0c;查看其上下左右的点#xff0c;如果新点没有被访问…采取从外层边界一步一步向内部拓展的策略具体来说一开始将最外面一层的点加入队列并标记这些点的坐标已经被访问
取出队列中高度最低的点将其弹出查看其上下左右的点如果新点没有被访问过分两种情况 1.如果新点的高度大于等于当前点将新点加入队列标记新点已经访问过了该点无法储水
2.如果新点的高度小于当前点则新点储水当前点的高度 - 新点的高度首先这么多水一定可以存因为当前点的高度是边界高度中最小的其次这是能存的最多的水因为再多就超过了当前点高度所以这个点能储存的水在这种策略下是所求的最大解将储水结果累加进ans并且将这个新点的高度改成当前点的高度后标记新点坐标已访问将新点加入队列中
不断重复以上操作直到队列为空
复杂度略
#includeiostream
#includecstdio
#includequeue
using namespace std;#define ll long longconst ll maxn305;
ll w,h,ans;
ll a[maxn][maxn],vis[maxn][maxn];
ll dx[]{-1,1,0,0},dy[]{0,0,-1,1};struct node{ll x,y,h;node(ll x0,ll y0,ll h0):x(x),y(y),h(h) {}bool operator (const node rhs) const {return hrhs.h;}
};int main()
{ios::sync_with_stdio(0);cin.tie(0);cinwh;for(ll i1;ih;i){for(ll j1;jw;j){cina[i][j];}}priority_queuenode q;//将最外一层加入队列for(int i1;iw;i){if(vis[1][i]0) {vis[1][i]1;q.push(node(1,i,a[1][i]));}if(vis[h][i]0) {vis[h][i]1;q.push(node(h,i,a[h][i]));}}for(int i1;ih;i){if(vis[i][1]0){vis[i][1]1;q.push(node(i,1,a[i][1]));}if(vis[i][w]0){vis[i][w]1;q.push(node(i,w,a[i][w]));}}/*while(q.size()){node tq.top();q.pop();printf((%lld,%lld)\n,t.x,t.y);}*/while(q.size()){node tq.top();q.pop();ll xt.x,yt.y,h1t.h;for(ll i0;i4;i){ll nxxdx[i],nyydy[i];if(nx1 || nxh || ny1 || nyw) continue;if(vis[nx][ny]) continue;if(a[nx][ny]h1) {q.push(node(nx,ny,a[nx][ny]));vis[nx][ny]1;}else {ansh1-a[nx][ny];q.push(node(nx,ny,h1));vis[nx][ny]1;}}}coutans\n;return 0;
}
