TopCoder SRM244 Div2 400Pts

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

典型的な電話機の番号の配列は次の通りである。

1	2	3
4	5	6
7	8	9
*	0	#

指の動きの量を二つのボタンのマンハッタン距離で定義する。電話番号を表す文字列が与えられたときに、電話番号を押すのに必要な指の動きの最小値を返せ。なお、指の初期位置は5に設定されているものとする。

私の解答はこちら。

public class PhonePad {
 public int fingerMovement(String phoneNumber) {
  // 2次元配列の座標で番号を表現
  String[][] pos = {{"1","2","3"},{"4","5","6"},{"7","8","9"},{"*","0","#"}};
  // 1文字ずつに分解
  String[] pushedArray = phoneNumber.split("");
  // 直前の指の座標、yが縦方向、xが横方向（画像処理的に）
  int x = 1;
  int y = 1;
  int totalMove = 0; // 指の動いた距離の合計
  for( int i=0 ; i<pushedArray.length ; i++ ){
   String current = pushedArray[i];
   for( int j=0 ; j<pos.length ; j++ ){
    for( int k=0 ; k<pos[j].length ; k++ ){
     if( pos[j][k].equals(current)){
      int aMove = Math.abs(y-j) + Math.abs(x-k);
      totalMove += aMove;
      y = j;
      x = k;
     }
    }
   }
  }
  return totalMove;
 }

}

得点は328.80/400、提出者の正解率は約90%。マンハッタン距離をどうやって表すかということがポイントで、2次元配列にすれば、インデックスの差がそのまま距離にできるというところがポイントだと思いました。レベル2の問題にしては簡単だったと思います。