Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-06-18SRM473(DIV1)

SRM473 div1 第一問(250点)

| SRM473 div1 第一問(250点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM473 div1 第一問(250点) - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10979

同じ方向を向いた状態でコマンドを実行すれば同じ結果になるので、

4回実行する間元の場所に戻れるかどうかを調べればOK。


public class SequenceOfCommands { 
  public String whatHappens(String[] commands) { 
    String all_command = ""; 
    for (String command : commands) { 
      all_command += command; 
    } 
    int x = 0, y = 0; 
    int dx[] = {0, 1, 0, -1}; 
    int dy[] = {1, 0, -1, 0}; 
    int dir = 0; 

    for (int t = 0 ; t < 4 ; t++) { 
      int len = all_command.length(); 
      for (int i = 0 ; i < len ; i++) { 
        char com = all_command.charAt(i); 
        switch (com) { 
          case 'S': 
            x += dx[dir]; 
            y += dy[dir]; 
            break; 
          case 'L': 
            dir = (dir + 4 - 1) % 4; 
            break; 
          case 'R': 
            dir = (dir + 1) % 4; 
            break; 
        } 
      } 
      if (x == 0 && y == 0) { 
        return "bounded"; 
      } 
    } 
    return "unbounded"; 
  } 
}

codercoder2010/06/19 06:16>>red pointは普通に計算していくだけ。
ここが線形探索だと計算量的に間に合わないですよ(1000000,100000,0,0,0 とか)

hama_DUhama_DU2010/06/19 18:07ほんとですね!longのキャスト直したらTLEしました!