#include <bits/stdc++.h>
int n, m, ans = 100500, g[10][10], a[10];
void dfs(int x) {
if(x == m) {
int gg[6][6], cnt = 0;
for (int i = 0; i < m; i++) {
cnt += std::min(a[i], n - a[i]);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
gg[i][j] = g[(i + a[j]) % n][j];
}
}
bool good = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(gg[i][j] != gg[i][0]) {
good = false;
}
}
}
if(good) {
ans = std::min(ans, cnt);
}
int count = 0;
std::map <std::vector <int>, int> mp;
int z[6][6], dp[6][6];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
std::vector <int> cur;
for (int k = 0; k < m; k++) {
cur.push_back(gg[i][(j + k) % m]);
}
if(mp.find(cur) == mp.end()) {
mp[cur] = ++count;
}
z[i][j] = mp[cur];
}
}
for (int j = 0; j < m; j++) {
dp[0][j] = std::min(j, m-j);
}
for(int i = 1; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i][j] = 1e9;
}
for (int j = 0; j < m; j++) {
for (int k = 0; k < m; k++) {
if(z[i][j] == z[i - 1][k]) {
dp[i][j] = std::min(dp[i][j], dp[i - 1][k] + std::min(j, m - j));
}
}
}
}
cnt += *std::min_element(dp[n - 1], dp[n - 1] + m);
ans = std::min(ans, cnt);
return;
}
for (int i = 0; i < n; i++) {
a[x] = i, dfs(x + 1);
}
}
int main() {
std::ios::sync_with_stdio(0); std::cin.tie(0);
std::cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", g[i] + j);
}
}
dfs(0);
std::cout << ans << "\n";
//std::cout.flush(); std::cin >> n;
}
Compilation message
riddicks.cpp: In function 'int main()':
riddicks.cpp:75:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
75 | scanf("%d", g[i] + j);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
