[백준 17822] 원판 돌리기

https://www.acmicpc.net/problem/17822

17822번: 원판 돌리기

요구 사항

1. 회전판 구현하기

deque로 회전판을 구현한다.

2. 회전판 회전하기

deque로 구현한 회전판을 시계방향, 시계반대 방향으로 돌릴 수 있도록 한다.

3. 조건 처리

 - 회전판 단위로 조건 찾기

 - now 회전판, next 회전판 조건 찾기

 - 조건 만족할 경우 0 삽입

 - 조건 없을 경우 완탐으로 평균 구해서 평균보다 크면 -1, 평균보다 작으면 +1

 

deque 사용하지 않고 bfs로도 풀이 가능

 

#include <iostream>
#include <deque>
#include <list>

using namespace std;
int n, m, k;
deque<int> dq[51];
list<int> li;
int visit[51][51];
void solve(int x, int d, int ki)
{
	int flag = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < m; j++)
			visit[i][j] = 0;
	int cnt = 1;
	//회전
	for (int i = x; i <= n; i = x*cnt)
	{
	//	cout << "i" << i << endl;
		for (int j = 0; j < ki; j++)
		{
			if (d == 0) {
				int value = dq[i].back();
				dq[i].pop_back();
				dq[i].push_front(value);
			//	cout << "j" << j << " " << d << " " <<value<<endl;
			}
			else {
				int value = dq[i].front();
				dq[i].pop_front();
				dq[i].push_back(value);
			//	cout << "j" << j << " " << d << " " << value << endl;
			}

		}
		cnt++;
	}
	//한 원판에서 인접한거 있는지 검사
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (j != m-1)
			{
				int nowvalue = dq[i][j];
				int nextvalue = dq[i][j + 1];
				if (nowvalue == 0 || nextvalue == 0)
					continue;
				if (nowvalue == nextvalue)
				{
					flag = 1;
					visit[i][j] = 1;
					visit[i][j + 1] = 1;
				}
			}
			else if (j == m-1)
			{
				int nowvalue = dq[i][j];
				int nextvalue = dq[i][0];
				if (nowvalue == 0 || nextvalue == 0)
					continue;
				if (nowvalue == nextvalue)
				{
					flag = 1;
					visit[i][j] = 1;
					visit[i][0] = 1;
				}
			}
		}
	}
	//같은 레벨에 있는거 같은지 검사
	for (int i = 0; i < m ; i++)
	{
		for (int j = 1; j < n; j++)
		{
			if (dq[j][i] == 0 || dq[j+1][i] == 0)
				continue;
			if (dq[j][i] == dq[j+1][i])
			{
				flag = 1;
				visit[j][i] = 1;
				visit[j+1][i] = 1;
			}
		}
	}
	//조건에 부합한거라면 0으로 바꿈
//	cout << "visit" << endl;
	if (flag == 1)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (visit[i][j] == 1)
					dq[i][j] = 0;
	//			cout << visit[i][j] << " ";
			}
	//		cout << endl;
		}
	}
	else if (flag == 0)
	{
		//cout << "ASDF" << endl;
		double val = 0;
		double cnt = 0;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				int nowv = dq[i][j];
				if (nowv != 0)
				{
					val += nowv;
					cnt++;
				}
			}
		}
		val = val / cnt;
	//	cout << "val" << val << endl;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (dq[i][j] != 0)
				{
					if (dq[i][j] > val)
						dq[i][j] = dq[i][j] - 1;
					else if (dq[i][j] < val)
						dq[i][j] = dq[i][j] + 1;
					else
						continue;
				}
			}
		}
	}


}
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int x;
			scanf("%d", &x);
			dq[i].push_back(x);
		}
	}
	for (int i = 0; i < k; i++)
	{
		int x, d, ki;
		scanf("%d%d%d", &x, &d, &ki);
		solve(x, d, ki);
	}
	int ans = 0;
	//cout << "dq" << endl;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (dq[i][j] != 0)
				ans += dq[i][j];
	//		cout << dq[i][j] << " ";
		}
	//	cout << endl;
	}
	cout << ans << endl;



}