450ptだからと甘く見ていたらまんまと失敗しました。
https://community.topcoder.com/stat?c=problem_statement&pm=14716
問題
(0,0)-(n-1,n-1)のマス目で構成されるグリッドがある。
マス(sx,sy)から(tx,ty)に移動したいが、1回の移動距離はユークリッド距離でd以上でなければならない。
最小何回の移動で到達できるか。
解法
1手で移動するならともかく、2手以上の場合は(sx,sy)(tx,ty)以外のマスを経由する必要がある。
その際、候補となりうるのは周辺部である。距離が遠いマスほど次に1手で移動できるので、あえて周辺部以外の点を通るメリットはない。
よって(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; } }
まとめ
本番4手かかるケースが思い浮かばなかったので3手上限と決めつけてしまった。
Hard終わって時間あったので、総当たりしておけばよかったかもね。