백준 17406 : 배열 돌리기 4 c++

www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

후기

1. 시간은 쫌 걸렸지만 난이도는 어렵지 않은 시뮬레이션 문제!!

2. 돌리기 작동시키는게 조금 오래걸린다

3. 순서 정하는거도 순열로 하면 편하다!!!!(이걸 얻어갑니다)

 

풀이

1. 순열로 명령어 순서 정하기

2. 정한 순서대로 회전 시행

3. 돌리기 다 끝났으면 답 업데이트

 

#include<iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct order {
	int r, c, s;
};

int n, m;
int k;
int map[51][51] = { 0, };
int temp[51][51];
int temp2[51][51];
int answer = 987654321;
vector<order> v;//입력받은 명령
vector<order> real;//내가 정한 순서!! 실제론 이거 쓸거야
int visited[7] = { 0, };

void rotate(order a)
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			temp2[i][j] = 0;//temp2에다가 돌린 값 저장하고 temp에다가 덮어 씌울 예정
		}

	for (int i = a.s; i > 0; i--)//s가 2면 두바퀴!
	{
		for (int k = a.c + i - 1; k >= a.c - i; k--)// 오른
		{
			temp2[a.r - i][k + 1] = temp[a.r - i][k];
		}

		for (int k = a.r + i-1; k >= a.r - i; k--)//아래
		{
			temp2[k + 1][a.c + i] = temp[k][a.c + i];
		}

		for (int k = a.c - i; k < a.c + i; k++)//왼쪽
		{
			temp2[a.r + i][k] = temp[a.r + i][k + 1];
		}

		for (int k = a.r - i; k < a.r + i; k++)//위
		{
			temp2[k][a.c - i] = temp[k+1][a.c - i];
		}
		temp2[a.r][a.c] = temp[a.r][a.c];


	}

	for (int q = a.r - a.s; q <= a.r + a.s; q++)
	{
		for (int w = a.c - a.s; w <= a.c + a.s; w++)
		{
			temp[q][w] = temp2[q][w];
		}
	}

}


void action()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			temp[i][j]= map[i][j];//초기화!!
		}

	for (int i = 0; i < real.size(); i++)//순서대로 돌려보고
	{
		rotate(real[i]);
	}

	int sum;
	for (int i = 1; i <= n; i++)//각행의 합
	{
		sum = 0;
		for (int j = 1; j <= m; j++)
		{
			sum += temp[i][j];
		}
		answer = min(answer, sum);
	}

}

void gogo()
{
	if (real.size() == v.size())//순서 다 정해진거임!!
	{
		action();
		return;
	}

	for (int i = 0; i < k; i++)
	{
		if (visited[i] == 0)
		{
			visited[i] = 1;
			real.push_back(v[i]);

			gogo();

			real.pop_back();
			visited[i] = 0;
		}
	}

}

int main()
{
	order a;
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= m; j++)
		{
			cin >> map[i][j];
		}
	for (int i = 0; i < k; i++)
	{
		cin >> a.r >> a.c >> a.s;
		v.push_back(a);
	}

	gogo();

	cout << answer<<endl;
	return 0;
}