AOJ-2243 : Step Step Evolution

Problem B: Step Step Evolution

ゲームセンターの矢印を踏むタイプの音ゲーが題材になってます。
譜面が与えられたときに、右足と左足を交互に使うように踏むのが良いらしい。
交互に使えなかった回数を数えて、出力する。ただし、足がクロスする配置は禁止。

注意しないといけないのは、右足から始める場合と左足から始める場合を試す必要があること。初期配置で足場が不正だった場合は判定を進めてはいけないこと。交差判定は、右足のx座標が左足より小さくならないように判定すればよい。最終的には、交互に使えなかった回数を出力して終了。

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2243

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

int panel[10] = {0,1,2,3,1,2,3,1,2,3};

const int LEFT = -1;
const int RIGHT = 1;

bool isValid(int left, int right)
{
	int left_x = panel[left];
	int right_x = panel[right];
	return (left_x > right_x) ? false : true;
}

int main()
{
	string S;
	while(true)
	{
		cin >> S;
		if( S == "#" ){ break; }
		
		vector<int> step;
		rep(i,S.length()){ step.push_back( S[i] - '0' ); }

		if(step.size() <= 2){ cout << 0 << endl; continue; }

		int ans = INT_MAX;
		int state, left, right;	
		rep(nth,2)
		{
			int cnt=0;
			if(nth){ //右足スタートと左足スタート
				left = step[0]; right = step[1]; state = LEFT;  
			}else{ 
				left = step[1]; right = step[0]; state = RIGHT;
			}

			if(!isValid(left,right)){ continue; }//初期配置で駄目な時
			
			REP( i, 2, step.size() )
			{
				if(state == RIGHT) //右足の場合
				{
					if(isValid(left,step[i])){
						right = step[i]; state = LEFT;
					}else{
						left = step[i]; cnt++; state = RIGHT;
					}
				}
				else //左足の場合
				{	
					if(isValid(step[i], right)){
						left = step[i]; state = RIGHT;
					}else{
						right = step[i]; cnt++; state = LEFT;
					}
				}
			}
			ans = min(ans, cnt);
		}
		cout << ans << endl;
	}
	return 0;
}