1185.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1185 on 2006-02-25 at 14:21:06 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 32;

int main()
{
	bool next[MAX][MAX];
	char ch, word[MAX], best[MAX];
	bool app[MAX];
	int i, j, n;
	
	while((ch = getchar()) != '#') {
		ungetc(ch, stdin);
		memset(next, false, sizeof(next)); memset(app, false, sizeof(app));
		for(n = 0; true; n++) {
			char nei[MAX]; ch = getchar();
			scanf(":%[A-Z]", nei);
			app[ch-'A'] = true;
			for(i = 0; nei[i] != 0; i++) app[nei[i]-'A'] = next[ch-'A'][nei[i]-'A'] = next[nei[i]-'A'][ch-'A'] = true;
			if(getchar() == '\n') break;
		}
		for(n = i = 0; i < MAX; i++)
			if(app[i]) word[n++] = i + 'A';
		word[n] = 0; int dis = MAX;
		do {
			int cd = 0;
			for(i = 0; i < n && cd < dis; i++)
				for(j = 0; j < n && cd < dis; j++)
					if(next[word[i]-'A'][word[j]-'A']) cd = max(cd, abs(i-j));
			if(cd < dis) { dis = cd; strcpy(best, word); }
		} while(next_permutation(word, word+n));
		for(i = 0; i < n; i++) printf("%c ", best[i]);
		printf("-> %d\n", dis);
	}
	
	return 0;
}