样例和udebug的数据都过了，但提交显示WA。

思路就是枚举全排列来搜索，里面加上最优性剪枝。

#include <cstdio>
#include <cstring>
#include <algorithm>
int a[9], n, ansa[9], pos[9];
bool g[9][9];
char s[1003];
int main() {
    while (scanf("%s", s) != EOF) {
        if (s[0] == '#')
            break;
        bool t[9] = {0};
        memset(g, 0, sizeof g);
        for (int i = 0; s[i];) {
            char now = s[i];
            t[s[i] - 'A'] = 1;
            i += 2;
            while (s[i] != ';' && s[i] != '\n' && s[i] != '\r' && s[i] != '\0')
                t[s[i] - 'A'] = 1, g[now - 'A'][s[i] - 'A'] = g[s[i] - 'A'][now - 'A'] = 1, ++i;//建边
            ++i;
        }
        for (n = 0; n < 8 && t[n]; n++)
            a[n] = n;
        int ans = 1 << 30;
        do {//搜索
            int mx = -(1 << 30);
            bool ok = 0;
            for (int i = 0; i < n; i++)
                pos[a[i]] = i;
            for (int i = 0; i < n; i++) {
                ok = 1;
                for (int j = 0; j < n; j++)
                    if (a[i] != j && g[a[i]][j]) {
                        int b = std::abs(pos[j] - i);//找距离
                        if (b >= ans) {
                            ok = 0;
                            break;
                        }
                        else
                            mx = std::max(mx, b);
                    }
                if (!ok)
                    break;
            }
            if (mx < ans && ok) {
                for (int i = 0; i < n; i++)
                    ansa[i] = a[i];
                ans = mx;
            }
        } while (std::next_permutation(a, a + n));
        for (int i = 0; i < n; i++)
            printf("%c ", ansa[i] + 'A');
        printf("-> %d\n", ans);
    }
    return 0;
}