AtCoder ARC #019 : C - 最後の森

Cでありながらいつもより正答率が低かった問題。
何とか解ききれてよかった。
リジャッジ後コードを修正しました。
http://arc019.contest.atcoder.jp/tasks/arc019_3

問題

2次元グリッドがあり、村(初期位置)・祠(中間地点)・城(ゴール)・障害物・敵がいる。
グリッド上で隣接マスに移動するコストは1である。

敵のいるマスは移動できないが、最大K匹まで敵を倒すことができる。1度倒した敵は復活しない。
村から祠を経由して城に到達する最小コストを答えよ。

解法

一見単なる最短経路問題だが、敵の存在がややこしい。
村から祠を経由して城に行く際、同じ場所を2回通る可能性があるが、敵を倒すのは1回で良いため、普通に最短経路を求めようとするとどの敵を倒したか覚えないといけないので面倒。

そこで合流地点が1か所あるとして、(村→合流地点)+(祠→合流地点)*2+(城→合流地点)の総コストが最小となり、かつ合計敵撃破数がK以下となるようにすればよい。
こんなイメージ。

村→→合→→城
      ↑
      ↓
      祠

まず村・祠・城から、(行,列,敵撃破数)を状態としてBFSし、最短経路を求める。
そして各合流地点に対し(村→合流地点)・(祠→合流地点)・(城→合流地点)の組みあわせを合計敵撃破数がKに収まるよう選び、(村→合流地点)+(祠→合流地点)*2+(城→合流地点)のコストを最小化する。

合流地点に敵がいる場合、敵を3重カウントしないよう注意。

int R,C,K;
string S[101];
int sx,sy,cx,cy,gx,gy;

int cost[3][101][101][101];

void solve() {
	int f,i,j,k,l,x,y,z;
	
	cin>>R>>C>>K;
	FOR(y,R) {
		cin>>S[y];
		FOR(x,C) {
			if(S[y][x]=='S') sx=x,sy=y,S[y][x]='.';
			if(S[y][x]=='C') cx=x,cy=y,S[y][x]='.';
			if(S[y][x]=='G') gx=x,gy=y,S[y][x]='.';
		}
	}
	
	set<pair<int,int> > SE;
	
	FOR(i,3) FOR(y,100) FOR(x,100) FOR(z,101) cost[i][y][x][z]=1<<25;
	cost[0][sy][sx][0]=cost[1][cy][cx][0]=cost[2][gy][gx][0]=0;
	SE.insert(make_pair(0,0*10000000+0*10000+sy*100+sx));
	SE.insert(make_pair(0,1*10000000+0*10000+cy*100+cx));
	SE.insert(make_pair(0,2*10000000+0*10000+gy*100+gx));
	
	while(!SE.empty()) {
		pair<int,int> k=*SE.begin();
		SE.erase(SE.begin());
		int type=k.second/10000000;
		int ccy=k.second/100%100,ccx=k.second%100,lk=k.second/10000%1000;
		if(k.first!=cost[type][ccy][ccx][lk]) continue;
		
		FOR(i,4) {
			int dx[]={1,-1,0,0};
			int dy[]={0,0,1,-1};
			int ty=ccy+dy[i],tx=ccx+dx[i];
			if(tx<0 || tx>=C || ty<0 || ty>=R) continue;
			if(S[ty][tx]=='T') continue;
			if(S[ty][tx]=='E'){
				if(lk<K && cost[type][ty][tx][lk+1]>cost[type][ccy][ccx][lk]+1) {
					cost[type][ty][tx][lk+1]=cost[type][ccy][ccx][lk]+1;
					SE.insert(make_pair(cost[type][ty][tx][lk+1],type*10000000+ty*100+tx+(lk+1)*10000));
				}
			}
			else {
				if(cost[type][ty][tx][lk]>cost[type][ccy][ccx][lk]+1) {
					cost[type][ty][tx][lk]=cost[type][ccy][ccx][lk]+1;
					SE.insert(make_pair(cost[type][ty][tx][lk],type*10000000+ty*100+tx+lk*10000));
				}
			}
		}
	}
	
	int ret=1<<30;
	FOR(y,R) FOR(x,C) {
		if(S[y][x]=='T') continue;
		FOR(i,3) FOR(z,K) cost[i][y][x][z+1]=min(cost[i][y][x][z],cost[i][y][x][z+1]);
		if(S[y][x]=='E') {
			FOR(i,K+1) for(j=0;j<=K-i;j++) {
				if(cost[0][y][x][i]+cost[1][y][x][j+1]+cost[2][y][x][K-i-j+1]<1<<25) 
				ret=min(ret,cost[0][y][x][i]+cost[1][y][x][j+1]*2+cost[2][y][x][K-i-j+1]);
			}
		}
		else {
			FOR(i,K+1) for(j=0;j<=K-i;j++) {
				if(cost[0][y][x][i]+cost[1][y][x][j]+cost[2][y][x][K-i-j]<1<<25) 
				ret=min(ret,cost[0][y][x][i]+cost[1][y][x][j]*2+cost[2][y][x][K-i-j]);
			}
		}
		
	}
	
	if(ret>=1<<25) _P("-1\n");
	else cout << ret << endl;
}

まとめ

合流地点を作るのがすぐ思いつけて良かった。
Codeforcesでそんな問題見た気がするのよね。