TopCoder SRM 729 Div1 Medium FrogSquare

450ptだからと甘く見ていたらまんまと失敗しました。
https://community.topcoder.com/stat?c=problem_statement&pm=14716

問題

(0,0)-(n-1,n-1)のマス目で構成されるグリッドがある。
マス(sx,sy)から(tx,ty)に移動したいが、１回の移動距離はユークリッド距離でd以上でなければならない。
最小何回の移動で到達できるか。

解法

1手で移動するならともかく、2手以上の場合は(sx,sy)(tx,ty)以外のマスを経由する必要がある。
その際、候補となりうるのは周辺部である。距離が遠いマスほど次に１手で移動できるので、あえて周辺部以外の点を通るメリットはない。
よって(sx,sy)(tx,ty)と周辺部の4(n-1)マスに関しダイクストラ法で最短移動回数を求めよう。

int D[4040];
int X[4040],Y[4040];

class FrogSquare {
	public:
	int minimalJumps(int n, int d, int sx, int sy, int tx, int ty) {
		int S,T,P=0;
		int i,x,y;
		
		if(sx==tx && sy==ty) return 0;
		FOR(y,n) FOR(x,n) {
			if(x==0 || x==n-1 || y==0 || y==n-1 || (sx==x&&sy==y) || (tx==x&&ty==y)) {
				X[P]=x;
				Y[P]=y;
				if(sx==x && sy==y) S=P;
				if(tx==x && ty==y) T=P;
				P++;
			}
		}
		
		queue<int> Q;
		FOR(i,P) D[i]=101010;
		Q.push(S);
		D[S]=0;
		while(Q.size()) {
			x=Q.front();
			Q.pop();
			if(x==T) return D[x];
			FOR(y,P) if(D[y]>D[x]+1) {
				if((X[x]-X[y])*(X[x]-X[y])+(Y[x]-Y[y])*(Y[x]-Y[y])>=d*d) {
					D[y]=D[x]+1;
					Q.push(y);
				}
			}
		}
		
		return -1;
	}
}

まとめ

本番４手かかるケースが思い浮かばなかったので３手上限と決めつけてしまった。
Hard終わって時間あったので、総当たりしておけばよかったかもね。