제출 #38862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38862		alenam0161	Riddick's Cube (IZhO13_riddicks)	C++14	100 / 100	23 ms	2016 KiB

riddicks

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

int R[10];
int C[10];
int M[10][10];
int n, m;

int getCell(int r, int c)
{
	if (r != 0)
	{
		c = (c + R[r - 1]) % m;
	}

	if (c != 0)
	{
		r = (r + C[c - 1]) % n;
	}

	return M[r][c];
}

bool checkRow(int r)
{
	int val = getCell(r, 0);

	for (int i = 1; i < m; i++)
	{
		if (getCell(r, i) != val)
			return false;
	}

	return true;
}

bool checkCol(int c)
{
	int val = getCell(0, c);

	for (int i = 1; i < n; i++)
		if (getCell(i, c) != val)
			return false;
	return true;
}

bool checkRows()
{
	for (int i = 0; i < n; i++)
		if (!checkRow(i))
			return false;
	return true;
}

bool checkCols()
{
	for (int i = 0; i < m; i++)
		if (!checkCol(i))
			return false;
	return true;
}

const int inf = 100500;


int evalCols()
{
	int ans = 0;
	for (int i = 0; i < m; i++)
	{
		ans += min(C[i], n - C[i]);
	}
	return ans;
}

int evalRows()
{
	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		ans += min(R[i], m - R[i]);
	}
	return ans;
}

int caseCheck()
{
	if (checkRows() || checkCols())
	{
		int ans1 = inf;
		int ans2 = inf;

		for (int i = 0; i < m; i++)
		{
			ans1 = min(ans1, evalRows());

			for (int j = 0; j < n; j++)
			{
				R[j]++;
				R[j] %= m;
			}
		}

		for (int i = 0; i < n; i++)
		{
			ans2 = min(ans2, evalCols());
			for (int j = 0; j < m; j++)
			{
				C[j]++;
				C[j] %= n;
			}
		}

		return min(inf, ans1 + ans2);
	}
	return inf;
}

int recCol(int pos)
{
	if (pos == m - 1)
	{
		return caseCheck();
	}

	int ans = inf;

	for (int i = 0; i < n; i++)
	{
		C[pos] = i;
		ans = min(ans, recCol(pos + 1));
	}

	return ans;

}

int recRow(int pos)
{
	if (pos == n - 1)
	{
		return recCol(0);
	}

	int ans = inf;

	for (int i = 0; i < m; i++)
	{
		R[pos] = i;
		ans = min(ans, recRow(pos + 1));
	}

	return ans;
}

int main()
{
//	freopen("riddicks.in", "r", stdin);
//	freopen("riddicks.out", "w", stdout);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> M[i][j];
	cout << recRow(0) << endl;
	return 0;
}

• Subtask 1: 100 / 100