AOJ : 2079 - Dance Dance Revolution

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2079

ダンスダンスレボリューションのシミュレートです。
このシミュレートにおいて、次のようなことが起こらないような、足の動き方なら"Yes"、起こってしまうなら"No"を出力する問題です。

• 同じ足場を連続で踏んでしまうような場合
• 右足と左足がクロスしてしまう場合

ただし、ここでは、右足と左足は、必ず交互に動かさなければいけません。
また、体は常に前を向いておかなければいかず、ゲーム途中に後ろを向いてステップを踏むことはできません。
はじめに動かす足は、左足・右足どちらからでもかまいません。

アルゴリズム

やるだけです。

最初に置く足だけ決めて、あとはシミュレートして、連続で同じ足場だったり、足がクロスする場合がないかどうか、文字列を見ていきます。
どっちの足から始めた場合も失敗だった場合は"No"、どちらか一方でも成功すれば"Yes"。
各足の位置情報は、上下左右で持つのではなく、-1 0 1 の三つのどれかで持つようにしています。
こうすることで、両足がクロスしたかどうかの判定を簡単に行うことができます。

余談ですが、このOBOGの公式データセットは、足のクロス判定をしなくても、「文字列の中に同じ文字が連続で出現するかどうか」の判定を行うだけで通ります。
とんでもないデータを作られましたｗ
というかこっちが勝手に問題を読み違えているだけな可能性もある？

プログラム

#include <stdio.h>
#include <string.h>

char s[100004];

int main(void){
    int i,j,n,len,rightFlg,foot[2];
    char before;
    scanf("%d",&n);

    while(n--){
        scanf("%s",s);

        len = strlen(s);

        for(j=0;j<2;j++){
            foot[0] = -1; //左足を左端に
            foot[1] = 1; //右足を右端に
            rightFlg = j; //一歩目を決める
            before = 0;

            for(i=0;i<len;i++){
                //前と同じステップならNo
                if(before == s[i]) break;

                switch(s[i]){
                case 'U':
                case 'D':
                    foot[rightFlg] = 0;
                    break;
                case 'R':
                    foot[rightFlg] = 1;
                    break;
                case 'L':
                    foot[rightFlg] = -1;
                    break;
                }

                //左足が右足より右側にあったらNo
                if(foot[0] > foot[1]) break;

                before = s[i];
                rightFlg = !rightFlg;
            }

            if(i == len) break;
        }

        printf("%s\n",j<2 ? "Yes" : "No");
    }

    return 0;
}