kmjp's blog

競技プログラミング参加記です

Codeforces #327 Div1 C. Three States

問題誤読した…。
http://codeforces.com/contest/590/problem/C

問題

2次元グリッドがある。
各セルは移動不可・道を作れば移動可・3国のどこかに属するのいずれかである。
各国のセルは互いに隣接マスを辿り連結している。

「移動不可」は移動できないが、「道を作れば移動可」は道を作れば移動可能となる。
3国に属するマスは常に移動可能である。

3国が互いに行き来可能となるためには最小何マスの道を作る必要があるか。

解法

「道を作れば移動可」のマスをコスト1、「3国に属するマス」のコストを0とし、各国のマスから各マスに移動するコストを求める。
3国のどこからでも移動可能なマスを1個総当たりし、3国からそこに至るコストの和を取ればよい。
ただしそのマスが「道を作れば移動可」の場合、そのマスのコストを3国分三重カウントしているので2引く必要がある。

int H,W;
string S[1010];
int cap[3][1001][1001];
int con[3][3];

int getcap(int type) {
	int y,x,i;
	priority_queue<pair<int,int> > Q;
	
	con[type][type]=1;
	FOR(y,H) FOR(x,W) {
		cap[type][y][x]=10101010;
		if(S[y][x]=='1'+type) {
			cap[type][y][x]=0;
			Q.push(make_pair(0,y*1000+x));
		}
	}
	
	while(Q.size()) {
		auto r=Q.top();
		Q.pop();
		int cy=r.second/1000,cx=r.second%1000;
		if(cap[type][cy][cx]!=-r.first) continue;
		FOR(i,4) {
			int dd[4]={1,0,-1,0};
			int ty=cy+dd[i],tx=cx+dd[i^1];
			if(tx<0 || tx>=W || ty<0 || ty>=H || S[ty][tx]=='#') continue;
			if(cap[type][ty][tx]>-r.first+(S[ty][tx]=='.')) {
				cap[type][ty][tx]=-r.first+(S[ty][tx]=='.');
				Q.push(make_pair(-cap[type][ty][tx],ty*1000+tx));
			}
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,3) FOR(x,3) con[y][x]=10101010;
	FOR(y,H) cin>>S[y];
	FOR(i,3) getcap(i);
	
	int mi=100010000;
	FOR(y,H) FOR(x,W) {
		if(S[y][x]=='.') mi=min(mi,cap[0][y][x]+cap[1][y][x]+cap[2][y][x]-2);
		if(isdigit(S[y][x])) mi=min(mi,cap[0][y][x]+cap[1][y][x]+cap[2][y][x]);
	}
	if(mi>10000000) return _P("-1\n");
	cout<<mi<<endl;
	
}

まとめ

1→3に行くとき2は通っちゃダメだと勘違いした…。