TopCoder SRM439 Div2 250Pts

Eclipse Coderがアップデートされて、ようやくArenaにログインできるようになったようなので演習再開。このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文についておおまかに説明する。

各セルに数値も含む、data[]という文字列型の長方形の格子が与えられる。この格子の中で、4つの角のセルがすべて同じ値を持つ最大の正方形を見つけよ。正方形の辺は格子の辺に平行でなければならないとする。もし、複数最大の正方形があるなら、1つを取り出せ。正方形中のセルの数を返せ。1つのセルも正方形なので、常に答えがあることに注意。

私の解答はこちら。

public class SquareOfDigits {

 public int getMax(String[] data) {
  int maxSize = 0;
  int[][] corner = new int[2][2]; // 正方形の4つの角の値を格納
  int nRow = data.length;
  int nCol = data[0].length();
  int rng = Math.min(nRow, nCol);
  for( int i=0 ; i<nRow ; i++ ){
   for( int j=0 ; j<nCol ; j++ ){ // (i,j)は正方形の左上の座標
    for( int n=0 ; n<rng ; n++ ){ // nは正方形のサイズ
     if( i+n >=nRow || j+n >= nCol ) continue;
     corner[0][0] = data[i].charAt(j);
     corner[0][1] = data[i].charAt(j+n);
     corner[1][0] = data[i+n].charAt(j);
     corner[1][1] = data[i+n].charAt(j+n);
     if( corner[0][0] == corner[0][1] && // 全部の角の値が同じなら
      corner[0][0] == corner[1][0] &&
      corner[0][0] == corner[1][1] ){
      // これまでにみつけた正方形の面積の最大値と比較
      maxSize = Math.max((n+1)*(n+1), maxSize);
     }
    }
   }
  }
  return maxSize;
 }

}

得点は218.49/250、1回のsubmitでシステムテストクリア。全部のパターンの探索方法の発見がポイントと思います。すぐに3重ループだと気づけば速いのでしょうけれど。