白準14891歯車

BOJ 14891

目標:ギアがK回回転して点数を求める.
条件:1<=K<=100、歯車は8歯からなる.

ソリューション

典型的な体現問題である.回転する歯車に隣接する歯車の左右が噛み合うと、異なる極であれば、その歯車も逆回転する.

#include<iostream>
#include<queue>
#include<string>
using namespace std;
string gear[4]; // L = 6 ,R = 2
int visit[4];
int N;

void turn(int x, int type){
	string tmp = "";
	if (type == 1){ // 시계방향
		tmp += gear[x][7];
		tmp += gear[x].substr(0,7);
	}
	else{ // 반시계방향
		tmp += gear[x].substr(1,7);
		tmp += gear[x][0];		
	}
	gear[x] = tmp;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	for (int i = 0; i < 4; i++){
		cin >> gear[i];
	}
	cin >> N;
	while(N--){
		int M, t;
		cin >> M >> t;
		M--;
		queue<int> Q;
		Q.push(M);
		visit[M] = t;
		while(!Q.empty()){
			int cur = Q.front();
			Q.pop();
			int next = cur-1;
			if (0 <= next && next < 4 && !visit[next] && gear[next][2] != gear[cur][6]){ // 좌우가 맞물린다면 반대방향으로 회전
				visit[next] = -visit[cur];
				Q.push(next);
			}
			next = cur+1;
			if (0 <= next && next < 4 && !visit[next] && gear[next][6] != gear[cur][2]){
				visit[next] = -visit[cur];
				Q.push(next);
			}
		}
		for (int i = 0; i < 4; i++){
			if (visit[i]){
				turn(i,visit[i]);
				visit[i] = 0;
			}
		}		
	}
	int ans = 0;
	for (int i = 0; i < 4; i++){
		if (gear[i][0] == '1'){
			ans += (1 << i);
		}
	}
	cout << ans << "\n";
	return 0;
}