Div2 500,Div1 250 SequenceOfCommands
問題
入力('S'は1歩進む,'L'は左に90°曲がる,'R'は90°右に曲がる)に従って移動する.この移動全体を繰り返した時,移動範囲は有限か?
考え方
とりあえず入力1回分の移動をしてみる.その結果としての移動と向きの変更がある.このとき,向きが同じであれば元と同じ移動ベクトルを繰り返すことになるので(移動ベクトルが0ベクトルでなければ)移動範囲は無限になる.
向きが元の方向と逆の場合はスタート地点との往復になるので移動範囲は有限になり,他の(元から90°違う)方向を向いている場合は移動ベクトルが90°変更されるが,どちらにしても結局4回繰り返すと元の地点に戻る(上に元と同じ方向を向く).
なので4回入力をパースして移動した結果,元と同じ地点にいるかどうかをチェックすればOK.
コード
#include <string> #include <vector> using namespace std; class SequenceOfCommands { public: string whatHappens(vector<string> commands) { string com; for( int i = 0 ; i < commands.size() ; ++i ) com += commands[i]; int x = 0, y = 0, dx = 1, dy = 0; for( int j = 0 ; j < 4 ; ++j ) for( int i = 0 ; i < com.size() ; ++i ) { switch( com[i] ) { case 'S': x += dx; y += dy; break; case 'R': { int t = dy; dy = -dx; dx = t; } break; case 'L': { int t = dy; dy = dx; dx = -t; } break; } } if( x == 0 && y == 0 ) return "bounded"; return "unbounded"; } };