2013年2月17日日曜日

TopCoder SRM461 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文についておおまかに説明する。

1000*1000の格子で表された草原がある。最初にウサギは(1, 1)の座標にいる(添字は1から始まる)。ウサギは水平方向と垂直方向の隣り合う地域へ1秒で移動することができ、その方法でのみ動くことができる。さて、あなたはウサギを罠にかけようとしている。そのために、いくつかの罠をしかけた。i番目の罠はtrapX[i]、trapY[i]で与えられ、それぞれ罠のX、Y座標を表している。ウサギが罠にはまる可能性が0とならない経過時間の最小値を返せ(罠にはまるというのは、罠のある位置にウサギが移動することをいう)。

私の解答はこちら。

public class TrappingRabbit {

 public int findMinimumTime(int[] trapX, int[] trapY) {
  int minSum = 2000;
  for( int i=0 ; i<trapX.length ; i++ ){
   minSum = Math.min(minSum, trapX[i]+trapY[i]);
  }
  return minSum-2;
 }

}

得点は246.48/250。1回のsubmitでシステムテストクリア。単純に一番マンハッタン距離の近い罠の座標から2を引くだけです。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計