Codeforces #420 Div2 D. Okabe and City

自分も運営もグダグダになってしまった回。
http://codeforces.com/contest/821/problem/D

問題

2次元のグリッドがあり、一部のセルは点灯している。
プレイヤーは左上角のセルから隣接する点灯セルをたどり右下角のセルに移動したい。

ここで、コスト1を払うことで任意の1列または1行の全セルを点灯できる。
新たな列または行のセルを点灯するとき、プレイヤーは元々点灯していたセルに乗った状態で、以前点灯したものを消したうえで新しいものを点灯しなければならない。
右下角セルに移動する最小コストを求めよ。

解法

セル数は多いため全セルで最短経路を探すのは計算量的に厳しいが、点灯セル数K個は少ないので、点灯セル間の移動コストを考えよう。
点灯セル間が移動できる条件は下記の通り。

• 元々隣接している
• 行または列の差が2以下である

あとはダイクストラ法の要領で解けばよい。
最後右下角セルがもともと点灯していない場合があるので注意。

int H,W,K;
int R[10101],C[10101],rid[10101],cid[10101];
vector<pair<int,int>> RR[10101];
vector<pair<int,int>> CC[10101];
priority_queue<pair<int,int>> Q;

int dist[10101];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(i,K) {
		cin>>R[i]>>C[i];
		R[i]--;
		C[i]--;
		dist[i]=101010;
		if(R[i]==0 && C[i]==0) {
			dist[i]=0;
			Q.push({0,i});
		}
	}
	
	int mi=101010;
	while(Q.size()) {
		int co=-Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		if(dist[cur]!=co) continue;
		
		if(R[cur]==H-1&&C[cur]==W-1) mi=min(mi,dist[cur]);
		if(R[cur]>=H-2||C[cur]>=W-2) mi=min(mi,dist[cur]+1);
		
		FOR(i,K) if(i!=cur) {
			if(abs(R[cur]-R[i])+abs(C[cur]-C[i])<=1) {
				if(dist[i]>dist[cur]) {
					dist[i]=dist[cur];
					Q.push({-dist[i],i});
				}
			}
			else if(abs(R[cur]-R[i])<=2 || abs(C[cur]-C[i])<=2) {
				if(dist[i]>dist[cur]+1) {
					dist[i]=dist[cur]+1;
					Q.push({-dist[i],i});
				}
			}
		}
	}
	if(mi==101010) mi=-1;
	cout<<mi<<endl;
	
	
}

まとめ

うーん。