Submission #38862

#TimeUsernameProblemLanguageResultExecution timeMemory
38862alenam0161Riddick's Cube (IZhO13_riddicks)C++14
100 / 100
23 ms2016 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...