TopCoder SRM458 Div2 250Pts

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

砂漠化がボブの島では深刻な問題である。ボブの島はセルの格子が長方形になっている。island[]というボブの島の状態が与えられる。i番目の要素のj番目の文字が島のi行j列の土地の状態を表し、Dが砂漠、Fが森を表す。砂漠の広がり方は1年後に砂漠が上下左右のセルに広がるというものである。砂漠はつねに砂漠でありつづける。T年後の砂漠のセル数を返すメソッドを作成せよ。

私の解答はこちら。

public class Desertification {

 public int desertArea(String[] island, int T) {
  int nRow = island.length;
  int nCol = island[0].length();
  int S = nRow * nCol; // セルの総数
  boolean[][] isDesert = new boolean[nRow][nCol]; // 今年砂漠かを記録
  boolean[][] nextDesert = new boolean[nRow][nCol]; // 翌年砂漠かを記録

  for( int i=0 ; i<nRow ; i++ ){ // 砂漠の位置を記録
   for( int j=0 ; j<nCol ; j++ ){
    if( island[i].charAt(j) == 'D' ) isDesert[i][j] = true;
   }
  }
  if( countTrueGrid(isDesert) == 0 ) return 0; // 砂漠がなければ砂漠はできないので0で終了

  for( int t=0 ; t<T ; t++ ){ // 砂漠の位置を拡散する
   for( int i=0 ; i<nRow ; i++ ){
    for( int j=0 ; j<nCol ; j++ ){
     if( isDesert[i][j] == true ){
      nextDesert[i][j] = true;
      if( i-1 >= 0 ) nextDesert[i-1][j] = true;
      if( j-1 >= 0 ) nextDesert[i][j-1] = true;
      if( j+1 < nCol ) nextDesert[i][j+1] = true;
      if( i+1 < nRow ) nextDesert[i+1][j] = true;
     }
    }
   }
   for( int i=0 ; i<nRow ; i++ ){
    for( int j=0 ; j<nCol ; j++ ){
     isDesert[i][j] = nextDesert[i][j];
    }
   }
   if( countTrueGrid(isDesert) == S ) return S; // 全部砂漠になったら終了
  }

  int nTrue = 0;
  for( int i=0 ; i<nRow ; i++ ){ // 最後の砂漠のセル数を数える
   for( int j=0 ; j<nCol ; j++ ){
    if( isDesert[i][j] ) nTrue++;
   }
  }
  return nTrue;
 }

 private int countTrueGrid(boolean[][] bl){ // 現在の砂漠のセル数をカウントする関数
  int n = 0;
  for( int i=0 ; i<bl.length; i++ ){
   for( int j=0 ; j<bl[i].length ; j++ ){
    if( bl[i][j] ) n++;
   }
  }
  return n;
 }

}

得点は203.52、1回のsubmitでシステムテストクリア。Tが10億まで取れるので、Tが大きい値になったときの対処が必要です。