2013年1月25日金曜日

TopCoder SRM455 Div2 250Pts

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

ペーチャは蜘蛛が好きである。彼は蜘蛛を長方形の格子の各セルに1匹づつ置いた。ペーチャは何年も蜘蛛について研究してきたので、すべての蜘蛛の動きを予想した。各秒の初めにすべての蜘蛛がセルから隣り合うセルのどれか1つに移動する(あるいは格子から離れる)。各セルにペーチャは蜘蛛の動きの方向を書いており、それはA[]という文字列型配列で与えられる。i番目の要素のj番目の文字はNSEWのいずれかであり、それぞれ北、南、東、西方向への移動を表している。もし格子の外側に移動したら、床に落ちる。1秒後に空いているセルの数を返せ。

私の解答はこちら。

public class SpidersOnTheGrid {

 public int find(String[] A) {
  int nRow = A.length;
  int nCol = A[0].length();
  boolean[][] isFilled = new boolean[nRow][nCol]; // 蜘蛛でそのセルが埋まっているかを記録
  for( int i=0 ; i<A.length ; i++ ){
   for( int j=0 ; j<A[0].length() ; j++ ){
    int xpos = i; // 蜘蛛の位置
    int ypos = j;
    if( A[i].charAt(j) == 'N' ){ // セルの内容に応じて蜘蛛を動かす
     xpos--;
    }else if( A[i].charAt(j) == 'S' ){
     xpos++;
    }else if( A[i].charAt(j) == 'E' ){
     ypos++;
    }else{ // West
     ypos--;
    }
    if( xpos < 0 || xpos >= nRow || ypos < 0 || ypos >= nCol ) continue; // 床に落ちる
    isFilled[xpos][ypos] = true; // 動いた先の座標をtrueに変える
   }
  }
  
  int nFilled = 0;
  for( int i=0 ; i<A.length ; i++ ){
   for( int j=0 ; j<A[0].length() ; j++ ){
    if( isFilled[i][j] == true ) nFilled++;
   }
  }
  return nRow*nCol-nFilled; // 空セルは全体から埋まっているセル数を引く
 }

}

得点は183.69/250、2回目のsubmitでシステムテストクリア。breakとcontinueを間違える凡ミスをした。

0 件のコメント:

コメントを投稿

フォロワー

ブログ アーカイブ

ページビューの合計