 /**//*
PROG: clocks
LANG: C
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max 100
 char str[9][6] = {"ABDE", "ABC", "BCEF", "ADG", "BDEFH", "CFI", "DEGH", "GHI", "EFHI"}, N[max][max], L[max];
int T[10], num, min;

int cmp(const void *a, const void *b)
  {
return strcmp((char*)a, (char *)b);
}
int Is(int s2[])
  {
int i;
for (i = 0; i < 9; i++)
 {
if (s2[i] != 0)
 {
return 0;
}
}
return 1;
}
void search(int s[], int length, int x)
  {
int i, s1[9];
char ch;
L[length] = x + '1';
length++;
L[length] = '\0';
if (length > min)
 {
return;
}
for (i = 0; i < 9; i++)
 {
s1[i] = s[i];//保存当前九个时钟的状态
}
for (i = 0; str[x][i] != '\0'; i++)
 {
ch = str[x][i] - 'A';
s1[ch] = (s1[ch] + 3) % 12; //拨动时钟
}
if (Is(s1))
 {
if (length < min)
 {
num = 0;
}
strcpy(N[num], L);//保存最少的波动方法
num++;
}
else
 {
for (i = x; i < 9; i++)
 {
T[i]++;//如果某种办法执行超过三次,即有了四次等于是无用功
if (T[i] < 4)
 {
search(s1, length, i);
}
T[i]--;
L[length] = '\0';
}
}
}

int main()
  {
FILE * fin = fopen("clocks.in", "r");
FILE * fout = fopen("clocks.out", "w");
min = 100;//随意设置一个值 ,保证最长的路径。
int s[9], i, j;
for (i = 0; i < 9; i++)
 {
fscanf(fin, "%d", &s[i]);
s[i] %= 12;
}
num = 0;
for (i = 0; i < 9; i++)
 {
search(s, 0, i);
}
qsort(N, num, 100 * sizeof(char), cmp);
for (i = 0; N[0][i + 1] != '\0'; i++)
 {
fprintf(fout, "%c ", N[0][i]);
}
fprintf(fout, "%c\n", N[0][i]);
return 0;
}
|