TopCoder SRM439 Div2 250Pts

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

dataという長方形グリッドの各セルに1桁の数字が入った文字列型配列が与えられる。4つの角にあるセルが同じ数字になる最大の正方形の中に含まれるセルの数を返すメソッドを作成せよ。なお、正方形の辺は常にグリッドに平行である(要は回転して正方形になるというケースは考慮しなくてもよい)。なお、1セルも正方形とみなすので、解答は常に存在する。

私の解答はこちら。

public class SquareOfDigits {

 public int getMax(String[] data) {
  int nRow = data.length;
  int nCol = data[0].length();
  int maxS = -1;
  int maxSide = Math.min(nRow, nCol);
  for( int n=0 ; n<maxSide ; n++ ){ // 探索する正方形の辺のサイズをnとしている
   for( int i=0 ; i<nRow-n ; i++ ){
    for( int j=0 ; j<nCol-n ; j++ ){
     // 正方形の存在条件
     if( data[i].charAt(j) == data[i].charAt(j+n) &&
      data[i+n].charAt(j) == data[i+n].charAt(j+n) &&
      data[i].charAt(j) == data[i+n].charAt(j) ){
      maxS = Math.max(maxS, (n+1)*(n+1));
     }
    }
   }
  }
  return maxS;
 }

}

得点は214.96/250、1回のsubmitでシステムテストクリア。SRM当日の正解率約66%。答えは常にn*nの形で与えられる。そのサイズにマッチするものを探索すればよいということに気付いてからは解答が速かったです。この問題はSRM前に開ける問題ということでウォーミングアップを兼ねて解きました。