kmjp's blog

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

TopCoder SRM 738 Div2 Hard MovingByPoints

Mediumの方が難しくないですか…。
http://community.topcoder.com/stat?c=problem_statement&pm=15108

問題

2次元座標上でN個の格子点にポイントがある。
このうち0番から(N-1)番の格子点に移動したい。

移動の際は、隣接する格子点に移動することを繰り返す。
ただしその座標にポイントがなければ移動できない。

0番から(N-1)番の格子点に移動する際、いくつかポイントを追加して移動できるようにしたい。
最小で何個ポイントを足す必要があるか。

解法

f(a,b) := 点aからbに至る経路で足さなければいけない点の数
とすると、f(a,b) := max(0,aとbのマンハッタン距離)となる。

求めたいのはf(0,N-1)なので、上記を元に最短経路問題を解くだけ。
Nが500なので、Warshall-Floyedでも間に合う。

int mat[501][501];

class MovingByPoints {
	public:
	int countMinimumPoints(int N, vector <int> X, vector <int> Y) {
		int x,y,z;
		FOR(x,N) FOR(y,N) mat[x][y]=max(0,abs(X[x]-X[y])+abs(Y[x]-Y[y])-1);
		FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][z]+mat[z][y]);
		return mat[0][N-1];
	}
}

まとめ

こっちMediumでもいいんじゃない…?