TopCoder SRM476 Div2 300Pts

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

N×Mの数字で埋められた行列がある。行列の要素は0～9である。この行列に対し、4つの操作が定義されている。それらは1行上にシフト(1番上の行は1番下に移動)、1行下にシフト(1番下の行は1番上に移動)、1列左にシフト（1番左の行は1番右に移動）、1列右にシフト(1番右の行は1番左に移動)というものである。1行しかなければ、1行上、下にシフトする操作は意味をもたないし、同様に、1列しかなければ1列左、右にシフトする操作は何も効果がないことに注意。matrix[]という、i番目の文字列のj番目の要素が行列の(i, j)要素を表す文字列型配列が与えられたとき、valueという値が一番左上に移動するのに必要な操作の回数の最小値を返せ。なお、valueに該当する値はmatrix中に複数存在することがある。左上に動かすべき要素がないときには-1を返せ。

public class MatrixShiftings {

 public int minimumShifts(String[] matrix, int value) {
  int nRow = matrix.length;
  int nCol = matrix[0].length();
  int minMove = nRow + nCol; // 最小移動回数のカウント
  int[][] array = new int[nRow][nCol]; // とりあえず数値として扱うことにする

  for( int i=0 ; i<nRow ; i++ ){
   char[] line = matrix[i].toCharArray();
   for( int j=0 ; j<nCol ; j++ ){
    array[i][j] = line[j] - '0';
   }
  }

  if( isExist(array, value) == false ) return -1; // 1個も検討すべき値がなければ-1で終了
  for( int i=0 ; i<nRow; i++ ){
   for( int j=0 ; j<nCol ; j++ ){
    if( array[i][j] == value ){
     int moveRow = Math.min(i, nRow-i); // 行方向に動かすべき最小回数
     int moveCol = Math.min(j, nCol-j); // 列方向に動かすべき最小回数
     minMove = Math.min(minMove, moveRow+moveCol); // valueが左上のセルに移動するまでの最小の移動回数を更新
    }
   }
  }

  return minMove;
 }

 private boolean isExist(int[][] a, int value){
  for( int i=0; i<a.length; i++ ){
   for( int j=0; j<a[0].length; j++ ){
    if( a[i][j] == value ) return true;
   }
  }
  return false;
 }
}

得点は254.13/300、1回のsubmitでシステムテストクリア。位置だけで左上のセルへの最小移動回数は決まるので、valueに合致するすべてのセルについてその回数を計算するだけ。コードは長いが、250点でも良さげ。