TopCoder SRM 706 Div1 Easy MovingCandies

いろいろグダグダだったけど何とか赤に戻った。
https://community.topcoder.com/stat?c=problem_statement&pm=14505

問題

N*Mの2次元グリッドがある。
各セルは埋まっているか埋まっていないかのいずれかである。
ここで隣接セルをたどり、左上角のセルから右下角のセルに移動したい。
その際、埋まっているセルしか通ることはできない。

最初の移動を開始する前に埋まっているマスを他の埋まっていないマスと任意の個数交換できるとする。
右下角のセルに移動する際、必要な最小交換数を求めよ。

解法

ダイクストラ法で以下の状態を更新しよう。同じ移動回数が同じなら、通過する空マス個数が少ない方が良い。
条件を満たす移動方法がない場合は、無限大に大きいと考える。
dp(r,c,p) := 左上角マスからp回移動してマス(r,c)に移動するまでに通過した空マスの個数の最小値

とはいえ、移動できる回数は埋まったマスの数が上限となるので、min(dp(N-1,M-1,p)) (pは元のグリッド中の埋まったマス以下の値)を答えればよい。

int dist[24][24][401];

class MovingCandies {
	public:
	
	int H,W;
	int minMoved(vector <string> t) {
		H=t.size();
		W=t[0].size();
		int y,x,i;
		int num=0;
		FOR(y,H) FOR(x,W) if(t[y][x]=='#') num++;
		FOR(y,H) FOR(x,W) FOR(i,H*W+2) dist[y][x][i]=1<<20;
		priority_queue<pair<int,int>> Q;
		dist[0][0][1]=(t[0][0]!='#');
		Q.push({-dist[0][0][1],1*10000});
		
		
		while(Q.size()) {
			int cy=Q.top().second%100;
			int cx=Q.top().second/100%100;
			int pass=Q.top().second/10000;
			int cost=-Q.top().first;
			Q.pop();
			if(pass>=num) continue;
			if(dist[cy][cx][pass]!=cost) continue;
			
			FOR(i,4) {
				int dd[4]={1,0,-1,0};
				int ty=cy+dd[i];
				int tx=cx+dd[i^1];
				if(ty<0 || ty>=H || tx<0 || tx>=W) continue;
				int add=t[ty][tx]=='.';
				if(dist[ty][tx][pass+1]>cost+add) {
					dist[ty][tx][pass+1]=cost+add;
					Q.push({-dist[ty][tx][pass+1],ty+tx*100+(pass+1)*10000});
				}
			}
		}
		
		int mi=2020;
		FOR(i,num+1) mi=min(mi,dist[H-1][W-1][i]);
		if(mi>=2020) mi=-1;
		return mi;
		
	}
}

まとめ

1Chalとれそうだったの時間切れで逃したのが残念。