文章插图
(自行脑补痛苦吼叫)
首先如果一开始就有连续的两个空地，那答案就是0 。剩下的情况就是我最后占用的两个位置一开始都被占据，或者其中有一个一开始被占据 。其中前者的两个位置一开始不可能属于同一张床，因为这样的话我们可以跟踪那张被移走的床，并让他把现在占据的位置让给我们 。这样还能少点步数(\([1]\)) 。"让出位置"的过程到底是什么样的？其实是一条路径，满足其中一端是一个空地，其他部分都是首尾相接的床，像这样：
文章插图
令路径的方向为从空地指向床(只是用来便于理解) 。每往路径里加一张床会有一个代价(p或q)，由新的床和上一张床的位置决定 。枚举我们最后占用的两个位置，如果其中有一个是空地，那么需要找出另一个位置到任意一个空地的最短路 。注意到路径每加一张床 ， 路径终点的横纵坐标之和的奇偶性都不会改变，所以不会出现最短路起点(注意上面说的最短路的方向)是需要留出的那个空地的情况 。如果两个位置都不是空地，那么我们需要考虑它们两个的最短路相交的情况 。但其实相交一定是不优的，枚举了也无所谓 。这是因为如果它们相交 ， 根据上面说的横纵坐标之和的奇偶性都不会改变的性质，路径上肯定有某张床的两个位置都要被移走，但是在\([1]\)处我们就说了这是不优的 。显然，这两条最短路的终点也不会重合，所以直接用它们的长度之和更新答案就行了 。
时间复杂度\(O(nmlog(nm))\) 。
比赛的时候没仔细想奇偶性不变的性质 ， 于是代码里就记录了到每个点的最短路、次短路和次次短路 ， 代码巨长 ， 还有一个地方没入队导致fst了 。我写的Dijkstra没有记录每个点是否已经转移过，但是每个点的入度都不大所以不影响复杂度 。
点击查看代码
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<n;++i)#define repn(i,n) for(int i=1;i<=n;++i)#define LL long long#define pii pair <int,int>#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){#ifdef LGSfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endif}void termin(){#ifdef LGSstd::cout<<"\n\nPROGRAM TERMINATED";#endifexit(0);}using namespace std;LL n,m,p,q,dx[]={-1,1,0,0},dy[]={0,0,-1,1},ans=1e18;string s[300010];char c[300010];vector <pair <LL,pii> > dist[3][300010];vector <pii> mat[300010];priority_queue <pair <pair <LL,pii>,pii>,vector <pair <pair <LL,pii>,pii> >,greater <pair <pair <LL,pii>,pii> > > qq;bool out(LL x,LL y){return x<0||x>=n||y<0||y>=m;}void upd(LL tox,LL toy,pair <LL,pii> val,LL fx,LL fy){if(fx!=tox&&fy!=toy) val.fi+=p;else val.fi+=q;bool hv=false;rep(i,3){if(dist[i][tox][toy].se==val.se){if(dist[i][tox][toy].fi>val.fi){dist[i][tox][toy].fi=val.fi;if(!hv) qq.push(mpr(val,mpr(tox,toy)));}return;}if(val.fi<dist[i][tox][toy].fi){if(!hv){hv=true;qq.push(mpr(val,mpr(tox,toy)));}swap(val,dist[i][tox][toy]);}}}void check(int x,int y,int xx,int yy){rep(i,3) if(dist[i][x][y].fi<1e18&&dist[i][x][y].se!=mpr(xx,yy))ans=min(ans,dist[i][x][y].fi);}void check2(int x,int y,int xx,int yy){rep(i,3) if(dist[i][x][y].fi<1e18&&dist[i][x][y].se!=mpr(xx,yy))rep(j,3) if(dist[j][xx][yy].fi<1e18&&dist[j][xx][yy].se!=mpr(x,y))if(dist[i][x][y].se!=dist[j][xx][yy].se) ans=min(ans,dist[i][x][y].fi+dist[j][xx][yy].fi);}int main(){fileio();cin>>n>>m>>p>>q;rep(i,n){scanf("%s",c);s[i]=c;}rep(i,3) rep(j,n) rep(k,m) dist[i][j].pb(mpr(1e18,mpr(-1,-1)));rep(j,n) rep(k,m) mat[j].pb(mpr(0,0));rep(i,n) rep(j,m){if(s[i][j]=='U') mat[i][j]=mpr(i+1,j),mat[i+1][j]=mpr(i,j);else if(s[i][j]=='L') mat[i][j]=mpr(i,j+1),mat[i][j+1]=mpr(i,j);}rep(i,n) rep(j,m) if(s[i][j]=='.'){rep(k,4){int xx=i+dx[k],yy=j+dy[k];if(out(xx,yy)|| !isalpha(s[xx][yy])) continue;upd(mat[xx][yy].fi,mat[xx][yy].se,mpr(0LL,mpr(i,j)),i,j);}}while(!qq.empty()){pair <pair <LL,pii>,pii> f=qq.top();qq.pop();auto val=f.fi;int x=f.se.fi,y=f.se.se;rep(i,4){int xx=x+dx[i],yy=y+dy[i];if(out(xx,yy)|| !isalpha(s[xx][yy])) continue;upd(mat[xx][yy].fi,mat[xx][yy].se,val,x,y);}}rep(i,n) rep(j,m){int ii=i+1,jj=j;if(!out(ii,jj)&&s[i][j]!='U'&&s[i][j]!='#'&&s[ii][jj]!='#'){if(s[i][j]=='.'&&s[ii][jj]=='.') ans=0;else{if(s[i][j]=='.') check(ii,jj,i,j);else if(s[ii][jj]=='.') check(i,j,ii,jj);else check2(i,j,ii,jj);}}ii=i;jj=j+1;if(!out(ii,jj)&&s[i][j]!='L'&&s[i][j]!='#'&&s[ii][jj]!='#'){if(s[i][j]=='.'&&s[ii][jj]=='.') ans=0;else{if(s[i][j]=='.') check(ii,jj,i,j);else if(s[ii][jj]=='.') check(i,j,ii,jj);else check2(i,j,ii,jj);}}}if(ans>=1e18) puts("-1");else cout<<ans<<endl;termin();}
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- Rated for Div. 2 Educational Codeforces Round 137 A-F
- Codeforces 1682 D Circular Spanning Tree
- Codeforces 1684 E. MEX vs DIFF
- Rated for Div. 2 Educational Codeforces Round 138 A-E
- [题解] Codeforces Dytechlab Cup 2022 1737 A B C D E 题解
- Div. 2 Codeforces Round #822 A-F
- Div. 2 Codeforces Round #823 A-D
- [题解] Codeforces Global Round 22 1738 A B C D E F 题解
- round函数怎么用 python的round函数怎么用
- turn around英语怎么读 round英语怎么读
