SRM 473 250pt: SequenceOfCommands

TopCoder

問題概要

右を向く、左を向く、一歩進むという命令列がある。この命令列を無限に繰り返したとき移動範囲は有限になるかどうかを判定する問題。

考えたこと

  • (当時はdyの値を間違えて-25をとってしまった記憶がある)
  • コマンド列を4回繰り返したら必ず前を向くことになるので、コマンド列を4回繰り替えして原点に戻るかどうかで判定すれば良い。

practiceで通ったコード

計算量O(|commands|)。

struct SequenceOfCommands {

	string whatHappens(vector <string> commands) {
		string cmd = accumulate(commands.begin(), commands.end(), string());
		cmd = cmd + cmd + cmd + cmd;

		int x = 0, y = 0, dir=0;
		for(int i=0; i<(int)cmd.size(); i++){
			if(cmd[i] == 'L'){
				dir = (dir + 1) % 4;
			}
			else if(cmd[i] == 'R'){
				dir = (dir + 3) % 4;
			}
			else if(cmd[i] == 'S'){
				x += dx[dir];
				y += dy[dir];
			}
		}

		return x == 0 && y == 0 ? "bounded" : "unbounded";
	}

};