VMKEY - Thế giới năm 1000003
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
typedef pair<int,int> ii;
const ii loc[]={ii(0,0),ii(0,1),ii(0,2),ii(1,0),ii(1,1),ii(1,2),ii(2,0),ii(2,1),ii(2,2),ii(3,0)};
const ii inf[]={ii(0,1),ii(0,2),ii(0,3),ii(0,4),ii(0,5),ii(0,6),ii(0,7),ii(0,8),ii(0,9),
ii(1,2),ii(1,3),ii(1,4),ii(1,5),ii(1,6),ii(1,7),ii(1,8),ii(1,9),
ii(2,3),ii(2,4),ii(2,5),ii(2,6),ii(2,7),ii(2,8),ii(2,9),
ii(3,4),ii(3,5),ii(3,6),ii(3,7),ii(3,8),ii(3,9),
ii(4,5),ii(4,6),ii(4,7),ii(4,8),ii(4,9),
ii(5,6),ii(5,7),ii(5,8),ii(5,9),
ii(6,7),ii(6,8),ii(6,9),
ii(7,8),ii(7,9),
ii(8,9)};
int x[11];
int f[55];
int log2[2222];
char s[400400];
int best,n;
int abs(const int &x) {
if (x<0) return (-x); else return (x);
}
int min(const int &x,const int &y) {
if (x<y) return (x); else return (y);
}
int max(const int &x,const int &y) {
if (x>y) return (x); else return (y);
}
int dis(const int &a,const int &b) {
return (abs(loc[x[a]].first-loc[x[b]].first)+abs(loc[x[a]].second-loc[x[b]].second));
}
int add(const ii &a) {
if (a.first==0) return (a.second-1);
if (a.first==1) return (a.second+7);
if (a.first==2) return (a.second+14);
if (a.first==3) return (a.second+20);
if (a.first==4) return (a.second+25);
if (a.first==5) return (a.second+29);
if (a.first==6) return (a.second+32);
if (a.first==7) return (a.second+34);
if (a.first==8) return (a.second+35);
}
void init(void) {
int i;
scanf("%s",s);
n=strlen(s);
for (i=0;i<45;i=i+1) f[i]=0;
for (i=0;i<n-1;i=i+1)
if (s[i]!=s[i+1])
f[add(ii(min(s[i],s[i+1])-48,max(s[i],s[i+1])-48))]++;
for (i=0;i<11;i=i+1) log2[1<<i]=i;
best=(int)1e9;
}
void update(void) {
int i;
int sum=0;
for (i=0;i<45;i=i+1) {
sum=sum+dis(inf[i].first,inf[i].second)*f[i];
if (sum>=best) return;
}
if (sum<best) best=sum;
}
void backtrack(const int &i,const int &s) {
int ts=(1<<10)-1-s;
while (ts>0) {
x[log2[ts&(-ts)]]=i;
if (i==9) update();
else backtrack(i+1,s|(ts&(-ts)));
ts=ts-(ts&(-ts));
}
}
void process(void) {
backtrack(0,0);
printf("%d",best);
}
int main(void) {
init();
process();
return 0;
}