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;
}

Download