VMKEY - Thế giới năm 1000003
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 4e5;
char s[N+1];
int n, f[10][10], pos[10][2], rpos[10][2];
void enter() {
scanf("%s", s);
n = strlen(s);
for(int i = 1; i < n; ++i) {
++f[s[i-1]-0x30][s[i]-0x30];
++f[s[i]-0x30][s[i-1]-0x30];
}
}
void backtrack(const int &p, const int &mask, const int &now, int &res) {
if(now >= res) return;
if(p == 10) {
res = now;
memcpy(rpos, pos, sizeof pos);
} else for(int v = 0; v < 10; ++v) if(~mask & 1 << v) {
pos[v][0] = p / 3; pos[v][1] = p % 3;
int add = 0;
for(int u = 0; u < 10; ++u) if(mask & 1 << u)
add += f[u][v] * (abs(pos[u][0] - pos[v][0]) + abs(pos[u][1] - pos[v][1]));
backtrack(p+1, mask | 1 << v, now + add, res);
}
}
int main() {
enter();
int res = INT_MAX;
backtrack(0, 0, 0, res);
printf("%d\n", res);
for(int i = 0; i < 10; ++i)
fprintf(stderr, "%d %d\n", rpos[i][0] + 1, rpos[i][1] + 1);
return 0;
}