1702.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1702 on 2005-12-31 at 00:25:50 */ 
#include <cstdio>
#include <cstring>

const int MAX = 128;
const int SIZE = 5;
const int INF = 1000000;

int n, d;
char word[MAX][SIZE+1], r[SIZE+1];
char tmp[SIZE+1] = "";
bool in[SIZE];

void DFS(int);
int cmp(char*, char*);
int com(char*, int, int);

int main()
{
	int i;

	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) scanf("%s", word[i]);
		d = INF; memset(in, false, sizeof(in));
		DFS(0);
		printf("%s is the median ranking with value %d.\n", r, d);
	}
	
	return 0;
}

void DFS(int o) {
	int i, m = 0;
	if(o == SIZE) {
		for(i = 0; i < n; i++) m += cmp(word[i], tmp);
		if(d > m) d = m, strcpy(r, tmp);
	} else {
		for(i = 0; i < SIZE; i++) {
			if(!in[i]) {
				in[i] = true; tmp[o] = i+'A';
				DFS(o+1);
				in[i] = false;
			}
		}
	}
}
int cmp(char* w1, char* w2)
{
	int i, j, p = 0;
	for(i = 0; i < SIZE; i++) {
		for(j = i+1; j < SIZE; j++) {
			if(com(w1, i, j) != com(w2, i, j)) p++;
		}
	}
	return p;
}
int com(char* w, int a, int b) {
	int i;
	for(i = 0; w[i] != 0; i++) {
		if(w[i] == a+'A') return 1;
		if(w[i] == b+'A') return 0;
	}
	return -1;
}