Codeforces #829 : Div1 D. The Beach

Div1Dの割には簡単？
https://codeforces.com/contest/1753/problem/D

問題

H*Wのグリッドがあり、一部は通過不可なマスである。
通過可能なマスに、いくつか2マス分を占めるベッドが置いてある。

このベッドを、どちらかのマスを中心に90度回転させるのにかかるコストはPである。
このベッドを、ベッドの頭または足側に1マス平行移動するのにかかるコストはQである。
もう1個ベッドを置けるようベッドを動かすのにかかる最小コストを求めよ。

解法

F(r,c) := r行c列目を空きマスにするための最小コスト
とし、隣接2マスのF(r,c)の和の最小値を求めればよい。
F(r,c)は普通にダイクストラ法の要領で計算できる。

int H,W;
ll A,B;
string S[303030];
vector<ll> dp[303030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>A>>B;
	priority_queue<pair<ll,int>> Q;
	FOR(y,H) {
		cin>>S[y];
		dp[y].resize(W);
		FOR(x,W) {
			if(S[y][x]=='.') {
				dp[y][x]=0;
				Q.push({0,y*W+x});
			}
			else {
				dp[y][x]=1LL<<60;
			}
		}
	}
	while(Q.size()) {
		ll co=-Q.top().first;
		int cy=Q.top().second/W;
		int cx=Q.top().second%W;
		Q.pop();
		if(dp[cy][cx]!=co) continue;
		
		if(cx>=2&&S[cy][cx-2]=='L'&&chmin(dp[cy][cx-2],co+B)) Q.push({-(co+B),cy*W+cx-2});
		if(cx+2<W&&S[cy][cx+2]=='R'&&chmin(dp[cy][cx+2],co+B)) Q.push({-(co+B),cy*W+cx+2});
		if(cy>=2&&S[cy-2][cx]=='U'&&chmin(dp[cy-2][cx],co+B)) Q.push({-(co+B),(cy-2)*W+cx});
		if(cy+2<H&&S[cy+2][cx]=='D'&&chmin(dp[cy+2][cx],co+B)) Q.push({-(co+B),(cy+2)*W+cx});
		if(cy+1<H&&cx+1<W&&(S[cy+1][cx+1]=='D'||S[cy+1][cx+1]=='R')&&chmin(dp[cy+1][cx+1],co+A)) Q.push({-(co+A),(cy+1)*W+cx+1});
		if(cy-1>=0&&cx+1<W&&(S[cy-1][cx+1]=='U'||S[cy-1][cx+1]=='R')&&chmin(dp[cy-1][cx+1],co+A)) Q.push({-(co+A),(cy-1)*W+cx+1});
		if(cy+1<H&&cx-1>=0&&(S[cy+1][cx-1]=='D'||S[cy+1][cx-1]=='L')&&chmin(dp[cy+1][cx-1],co+A)) Q.push({-(co+A),(cy+1)*W+cx-1});
		if(cy-1>=0&&cx-1>=0&&(S[cy-1][cx-1]=='U'||S[cy-1][cx-1]=='L')&&chmin(dp[cy-1][cx-1],co+A)) Q.push({-(co+A),(cy-1)*W+cx-1});
	}
	ll mi=1LL<<60;
	FOR(y,H) FOR(x,W) {
		if(y) mi=min(mi,dp[y-1][x]+dp[y][x]);
		if(x) mi=min(mi,dp[y][x-1]+dp[y][x]);
	}
	if(mi==1LL<<60) mi=-1;
	cout<<mi<<endl;
}

まとめ

本番もかなりすんなり解けている。