oj.uz

답안 #38862

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
38862 2018-01-07T11:37:15 Z alenam0161 Riddick's Cube (IZhO13_riddicks) C++14
100 / 100
 23 ms 2016 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2016 KB Output is correct
2 Correct 0 ms 2016 KB Output is correct
3 Correct 0 ms 2016 KB Output is correct
4 Correct 0 ms 2016 KB Output is correct
5 Correct 0 ms 2016 KB Output is correct
6 Correct 0 ms 2016 KB Output is correct
7 Correct 0 ms 2016 KB Output is correct
8 Correct 0 ms 2016 KB Output is correct
9 Correct 0 ms 2016 KB Output is correct
10 Correct 0 ms 2016 KB Output is correct
11 Correct 0 ms 2016 KB Output is correct
12 Correct 0 ms 2016 KB Output is correct
13 Correct 9 ms 2016 KB Output is correct
14 Correct 13 ms 2016 KB Output is correct
15 Correct 23 ms 2016 KB Output is correct
16 Correct 19 ms 2016 KB Output is correct
17 Correct 9 ms 2016 KB Output is correct
18 Correct 9 ms 2016 KB Output is correct
19 Correct 9 ms 2016 KB Output is correct
20 Correct 9 ms 2016 KB Output is correct