TopCoder SRM406 Div2 250Pts

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

grid[]という文字列型配列による長方形型のセルについて考える。"X"という文字が入ったセルは埋まっていることを示し、"."という文字はそのセルが空いていることを示している。二つのセルが同じ辺を共有しているとき、二つのセルは直交に隣合っている(orthogonal neighbors)といい、互いに斜めの位置にある場合、二つのセルは対角に隣り合っている(adjacent neighbors)という。もし、あるセルが空白で、かつ直交に隣り合うセルと斜めに隣り合うセルがすべて埋まっているのであれば、そのセルを1-happyということにする。あるセルが空白で、直交に隣り合うセルがすべて埋まっていて、斜めに隣あうセルが1つ以上空白であるとき、そのセルを2-happyという。あるセルが空白で、斜めに隣り合うセルがすべて埋まっているが、1つ以上直交に隣り合うセルに空白があるとき、そのセルは3-happyという。1-happyに該当するセル、2-happyに該当するセル、3-happyに該当するセルの数を求め、それらの3つの要素からなる整数型の配列を返すメソッドを作成せよ。

私の解答はこちら。

public class HappyCells {

 public int[] getHappy(String[] grid) {
  int[] happy = new int[3];
  int nrow = grid.length;
  int ncol = grid[0].length();
  // 自身を含む周囲9マスの相対的な位置、xは上下方向、yは左右方向
  // 添え字は左上から右下に向かって大きくなる。注目しているセルは5番目になる
  int[] x = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
  int[] y = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
  for( int i=0 ; i<nrow ; i++ ){
   for( int j=0 ; j<ncol ; j++ ){
    int diag = 0; // 直交に隣り合うセルの.の数
    int orth = 0; // 斜めに隣り合うセルの.の数
    if( grid[i].charAt(j) != '.') continue; // .のセル以外は考えなくて良い
    for( int k=0 ; k<x.length ; k++ ){
     if( k == 4 ) continue; // 5番目のセル(つまり周囲を注目すべきセル)は考慮しない
     int xpos = i+x[k];
     int ypos = j+y[k];
     // 長方形の範囲を超える箇所では考える必要はない
     if( xpos < 0 || xpos >= nrow || ypos < 0 || ypos >= ncol ) continue;
     if( grid[xpos].charAt(ypos) == '.' && k % 2 == 0 ){
      diag++;
     }else if( grid[xpos].charAt(ypos) == '.' && k % 2 == 1 ){
      orth++;
     }
    }
    // 得られた周囲の.の数から、加算すべき配列の添字を決める
    if( diag == 0 && orth == 0 ){
     happy[0]++;
    }else if( diag > 0 && orth == 0 ){
     happy[1]++;
    }else if( diag == 0 && orth > 0 ){
     happy[2]++;
    }
   }
  }
  return happy;
 }

}

196.97/250、1回のsubmitでシステムテストクリア。変数の書き換えなどしていたので、1点ぐらいは下げたのではなかろうか...