[アルゴリズム]白駿14891
3369 ワード
質問する
質問リンク
これは歯車を転がして最後の状態を調整する問題です.
さすが三星問題、シミュレーション問題、論理は簡単ですが、扱う変数条件などは厳しいです.
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;
}
Reference
この問題について([アルゴリズム]白駿14891), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-백준-14891
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
/**
* 백준 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;
}
Reference
この問題について([アルゴリズム]白駿14891), 我々は、より多くの情報をここで見つけました https://velog.io/@shininghyunho/알고리즘-백준-14891テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol