[アルゴリズム]白駿14891


質問する


質問リンク
これは歯車を転がして最後の状態を調整する問題です.

さすが三星問題、シミュレーション問題、論理は簡単ですが、扱う変数条件などは厳しいです.
n極s極を0と1に設定し,回転の論理を混同した.
したがって,複数の関数を作成するには,主関数に論理のみを接続することが重要であるようである.
論理順序.
1.再帰呼び出しで両側が回転可能かどうかをチェックする(RotateCheck)
2.検査完了後、検査内容を回転させる(rotate)
各回転の方向が異なるので、回転中に1つずつ処理(RotateOne)
3.スコアリング(score)
注意すべきことが多すぎるせいか、のこぎりの数と最初の0からか1からか分かりません.
時間がかかった.

code

/**
 * 백준 14891
 * 시뮬레이션
*/
#include <bits/stdc++.h>
#define gearNum 4
#define wheelNum 8

using namespace std;

int gear[gearNum][wheelNum];
int head[gearNum];
bool isRotate[gearNum];

void rotateOne(int wheel,int d){
    if(d==1){
        // 시계
        head[wheel]=((head[wheel]-1+wheelNum)%wheelNum);
    }else{
        head[wheel]=((head[wheel]+1)%wheelNum);
    }
}
void rotateCheck(int wheel,int d){
    if(isRotate[wheel]) return;
    isRotate[wheel]=true;
    // left check
    bool lOk=false;
    if(wheel-1>=0 && !isRotate[wheel-1]){
        // wheel head+6이랑 wheel-1의 2랑 다른 극일때
        if(gear[wheel][(head[wheel]+6)%wheelNum]!=gear[wheel-1][(head[wheel-1]+2)%wheelNum]){
            lOk=true;
        }
    }
    // right check
    bool rOk=false;
    if(wheel+1<gearNum && !isRotate[wheel+1]){
        // wheel head+2랑 wheel+1의 6이랑 다를때
        if(gear[wheel][(head[wheel]+2)%wheelNum]!=gear[wheel+1][(head[wheel+1]+6)%wheelNum]){
            rOk=true;
        }
    }

    int od=(d==1)?-1:1;
    if(lOk) rotateCheck(wheel-1,od);
    if(rOk) rotateCheck(wheel+1,od);
}
void rotate(int start,int d){
    int od=(d==1)?-1:1;
    for(int i=0;i<gearNum;i++){
        if(isRotate[i]){
            // 같은 방향
            if((start+i)%2==0){
                rotateOne(i,d);
            }
            else{
                rotateOne(i,od);
            }
        }
    }
}
int score(void){
    int ret=0;
    int scores[gearNum]={1,2,4,8};
    for(int i=0;i<gearNum;i++){
        ret+=(gear[i][head[i]]==1?scores[i]:0);
    }
    return ret;
}
int main(void){
    for(int i=0;i<gearNum;i++){
        head[i]=0;
        for(int j=0;j<wheelNum;j++){
            scanf("%1d",&gear[i][j]);
        }
    }
    int order=0;
    cin>>order;
    while(order--){
        int wheel,d;
        cin>>wheel>>d;
        wheel--; // 0번 부터 시작
        fill(isRotate,isRotate+gearNum,false);
        rotateCheck(wheel,d);
        rotate(wheel,d);
    }
    cout<<score()<<endl;
}