1. 首頁 > 生活百科 > >

Div. 1/Div. 2 Codeforces Round #829 1753 A B C D 題解( 二 )

生活百科


文章插圖
(自行腦補痛苦吼叫)
首先如果一開始就有連續的兩個空地，那答案就是0 。剩下的情況就是我最后占用的兩個位置一開始都被占據，或者其中有一個一開始被占據 。其中前者的兩個位置一開始不可能屬于同一張床，因為這樣的話我們可以跟蹤那張被移走的床，并讓他把現在占據的位置讓給我們 。這樣還能少點步數(\([1]\)) 。"讓出位置"的過程到底是什么樣的？其實是一條路徑，滿足其中一端是一個空地，其他部分都是首尾相接的床，像這樣：

Div. 1/Div. 2 Codeforces Round #829 1753 A B C D 題解

文章插圖
令路徑的方向為從空地指向床(只是用來便于理解) 。每往路徑里加一張床會有一個代價(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();}

推薦閱讀