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でもいいんじゃない…?