가지치기 검색

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10;
int id[256], letter[maxn], vis[maxn], edge[maxn][maxn], n, head, P[maxn], bestP[maxn], ans;
void map_id_letter(const string &s)
{
    n = 0;
    for (int c = 'A'; c <= 'Z'; c++)
        if (s.find(c) != -1)
        {
            id[c] = n;
            letter[n] = c;
            n++;//                
        }
}
void bandwidth(int dis, int width)
{
    if (dis == n)
    {
        ans = width;
        memcpy(bestP, P, sizeof(P));
        return;
    }
    else
        for (int i = 0; i < n; i++)
            if (!vis[i])
            {
                vis[i] = 1;
                P[dis] = i;
                int new_w = 0;
                for (int j = 0; j < dis; j++)
                    if (edge[i][P[j]])
                    {new_w = dis - j; break;}//                    ，    
                int cur_bw = max(width, new_w);
                if (cur_bw < ans)
                    bandwidth(dis + 1, cur_bw);
                vis[i] = 0;
            }
}
int main(int argc, char const *argv[])
{
    string inp;
    while (cin >> inp && inp[0] != '#')
    {
        map_id_letter(inp);
        memset(edge, 0, sizeof(edge));
        for (int i = 0; i < inp.size(); i++)
        {
            if (i == 0 || inp[i - 1] == ';')
                head = inp[i];
            else if (isalpha(inp[i]))//   
                edge[id[head]][id[inp[i]]] = 1, edge[id[inp[i]]][id[head]] = 1;
        }
        ans = n;
        bandwidth(0, 0);
        for (int i = 0; i < n; i++)
            printf("%c ", letter[bestP[i]]);//            
        printf("-> %d
", ans);
    }
    return 0;
}