はじめに

問題: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2243
ソースコード: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1365966
言語はJava
実装よいうよりは考える問題なので、答えを見る際は注意。

問題文概訳

日本のゲーム会社が、Step Step Evolution というゲームを開発した。このゲームのプレイ方法はシンプルだ。プレイヤーはダンス台に立ち、スクリーンに表示された矢印にしたがってパネルを踏む。

Step Step Evolution には8個の矢印がある。上、右上、右、右下、下、左下、左、左上である。矢印は画面の下から上に向かって出てくる。画面の一番上に矢印が来たら、それに合わせて図で示したようなパネルを踏むのである。

このゲームでは、以下の条件に従わなければならない

プレーの開始時を除き、あなたは指示されたパネル以外のパネルを踏んではいけない。
パネルを踏んだら、その足はそのままで、次の矢印が来るまで離してはいけない。
左足は今右足があるパネルよりも右のパネルを踏めない。また、右足は今左足があるパネルよりも左のパネルは踏めない。

例えば、図2において、最初の図と2つ目の図は、条件を満たした状態だが、最後の図だけ、3つ目の条件を満たしていない状態となる。

プレイの最初は、右足と左足はどこに置いてあってもよい。また、右足と左足、どちらからステップをはじめてもよい。

このゲームの美しいプレイとして、「Natural footstep style」というプレイスタイルが有名である。これは、右足と左足で交互にパネルを踏むスタイルである。しかし、矢印の並びが複雑になってくると、このプレースタイルは難しくなる。

あなたの友達は、あなたのためにこのゲームの譜面（矢印がどのような順番で出てくるか示すもの）を作った。あなたは、この譜面で何箇所「Natural footstep style」が崩れるかに興味があった。つまり、最も最適なステップをした場合、同じ足で2回連続ステップを踏まなければいけない箇所は、何箇所まで減らせるか、ということだ。

入力

入力はいくつかのデータセットを含む。それぞれのデータセットは1行で、5以外の1から9までの数字の列である。それぞれの数字が示す矢印の方向は図3の通りである。

数字は1個以上100000個以下入力される。同じ数字が連続することはない。すべての入力の終わりは # で示される。

出力

それぞれのデータセットに対して、Natural footstep style が崩れる回数を1行で出力せよ。

方針

交互に踏める限り貪欲に交互に踏んでいって問題ない。条件3の制約のため無理な場合だけ同じ足を使う
最初にスタートする足も重要。これは右足からスタートした場合と左足からスタートした場合両方試して最小値を取る
実装は頑張る（コード量はそんなに多くならない）

実装

class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            char[] seq = br.readLine().toCharArray();
            if(seq[0] == '#') break;
            System.out.println(Math.min(check(seq, 0), check(seq, 1)));
        }
    }
    
    static int check(char[] seq, int foot){
        int[] pannel_on_foot = {0, 2};
        int cnt = 0;
        for(int i = 0; i < seq.length; i++){
            int pannel = ((int)(seq[i] - '0') - 1) % 3;
            if(foot == 0){
                // 踏み出す足が左足の場合
                // 右足よりも右には行けない
                if(pannel_on_foot[1] < pannel){
                    cnt++;
                    pannel_on_foot[1] = pannel;
                }else{
                    pannel_on_foot[0] = pannel;
                    foot = (foot + 1) % 2;
                }
            }else{
                // 右足の場合
                // 左足よりも右には行けない
                if(pannel < pannel_on_foot[0]){
                    cnt++;
                    pannel_on_foot[0] = pannel;
                }else{
                    pannel_on_foot[1] = pannel;
                    foot = (foot + 1) % 2;
                }
            }
        }
        return cnt;
    }
}