Codeforces #619 Div2 F. Super Jaber

思いつけば難しくない問題。
https://codeforces.com/contest/1301/problem/F

問題

H*Wのグリッドが与えられる。
各セルには1～Kの数値のいずれかが設定されている。

以下のクエリに順次答えよ。
2つのセルs,tが指定される。
隣接セルへの移動または現在いるセルと同じ値を持つセルへの移動が時間1で行える時、セルsから、もうセルtへ至る最短の時間を求めよ。

解法

前処理として以下を求めておく。
前者はBFS、後者はkが小さいのでWarshall-Floyedで良い。

• 各セルcから、各数値vを持つ最寄りのセルへの最短時間f(c,v)
• ある数値xのセルから、別の数値yのセルへの最短時間g(x,y)

各クエリについては、隣接セルだけをたどるケースのほか、数値x,yを総当たりしてf(u,x)+g(x,y)+f(v,y)の最小値を求めればよい。

int H,W,K;
int Q,R1,C1,R2,C2;

int A[1010][1010];
int D[1010][1010][41];
int E[41][41];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&H,&W,&K);
	FOR(y,H) FOR(x,W) {
		scanf("%d",&i);
		A[y][x]=i-1;
	}
	FOR(y,K) FOR(x,K) E[y][x]=(y==x)?0:202020;
	
	FOR(i,K) {
		queue<int> Q;
		FOR(y,H) FOR(x,W) {
			if(A[y][x]==i) {
				D[y][x][i]=0;
				Q.push(y*1000+x);
			}
			else {
				D[y][x][i]=202020;
			}
		}
		while(Q.size()) {
			y=Q.front()/1000;
			x=Q.front()%1000;
			Q.pop();
			E[A[y][x]][i]=min(E[A[y][x]][i],D[y][x][i]);
			
			FOR(j,4) {
				int dd[4]={1,0,-1,0};
				int ty=y+dd[j];
				int tx=x+dd[j^1];
				if(ty<0||ty>=H||tx<0||tx>=W) continue;
				if(D[ty][tx][i]>D[y][x][i]+1) {
					D[ty][tx][i]=D[y][x][i]+1;
					Q.push(ty*1000+tx);
				}
			}
		}
	}
	FOR(r,K) FOR(x,K) FOR(y,K) E[x][y]=min(E[x][y],E[x][r]+1+E[r][y]);
	
	scanf("%d",&Q);
	while(Q--) {
		scanf("%d%d%d%d",&R1,&C1,&R2,&C2);
		R1--,C1--,R2--,C2--;
		int ret=abs(R2-R1)+abs(C2-C1);
		
		FOR(x,K) {
			ret=min(ret,D[R1][C1][x]+D[R2][C2][x]+1);
			FOR(y,K) ret=min(ret,D[R1][C1][x]+D[R2][C2][y]+E[x][y]+2);
		}
		_P("%d\n",ret);
	}
	
	
}

まとめ

ここらへん最終問が簡単なDiv2が続く？