yukicoder : No.971 いたずらっ子

これは★2.5でもいい気がするな。
https://yukicoder.me/problems/no/971

問題

グリッド上で、左上角マスから右または下の隣接マスへの移動を繰り返し、右下角マスへ移動することを考える。
一部のマスには障害物がある。障害物は、いったんそのマスに入った後、それを最初のマスに持っていくことで撤去できる。
それ以外の場所に持っていくことはできない。

右下角マスへの最少移動マス数を求めよ。

解法

(r,c)をR行C列目のマスとする。障害物のないマスへの侵入コストを1、あるマスへの侵入コストを障害物を片付けて再侵入する場合を考えて(r-1+c-1+1)ととれば、単なるDPになる。

int H,W;
string S[2020];
ll D[2020][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) D[y][x]=1LL<<60;
	}
	D[0][0]=0;
	FOR(y,H) FOR(x,W) {
		if(y+1<H) D[y+1][x]=min(D[y+1][x],D[y][x]+(S[y][x]=='k'?y+x+1:1));
		if(x+1<W) D[y][x+1]=min(D[y][x+1],D[y][x]+(S[y][x]=='k'?y+x+1:1));
	}
	cout<<D[H-1][W-1]<<endl;
		
}

まとめ

コードも短いしね。