Codeforces #327 Div1 C. Three States

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

問題

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

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

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

解法

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

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は通っちゃダメだと勘違いした…。