[shkola] Ima 15-ka

Dotuk sme s 83 tochki :o).
-- 
Rangel Dokov
#include <stdio.h>

#define MAXN            256
#define A                       0
#define B                       1
#define C                       2

int sets[3][MAXN];
int parent[MAXN];
int depth;
int best_count = 256;

int calc_dist(int a, int b) {
        int i;
        int count = 0;

        for (i = 0; i <= 7; i++)
                if ((a&(1<<i)) != (b&(1<<i)))
                        count++;

        return count;
}

void add_solution() {
        int i;

        if (depth >= best_count)
                return;

        best_count = depth;
        printf("%d", depth);
        for (i = 0; i < MAXN; i++)
                if (sets[B][i])
                        printf(" %d", i);
        printf("\n");
}

void DFS(int node) {
        int i;
        int sol;

        depth++;
        sets[C][node] = 0;
        sets[B][node] = 1;

        for (i = 0; i < MAXN; i++)
                if (sets[C][i] && (calc_dist(i, node) <= 2)) {
                        sets[C][i] = 0;
                        sets[A][i] = 1;
                        parent[i] = node;
                }

        sol = 1;
        for (i = 0; i < MAXN; i++)
                if (sets[C][i]) {
                        sol = 0;
                        if (i < node)
                                break;

                        if (depth + 1 < best_count)
                                DFS(i);
                        else
                                break;
                }

        if (sol == 1)
                add_solution();

        for (i = 0; i < MAXN; i++)
                if (parent[i] == node) {
                        parent[i] = -1;
                        sets[A][i] = 0;
                        sets[C][i] = 1;
                }

        sets[C][node] = 1;
        sets[B][node] = 0;
        depth--;
}

int main() {
        int i;

        for (i = 0; i < MAXN; i++) {
                sets[C][i] = 1;
                parent[i] = -1;
        }

        for (i = 0; i < MAXN; i++)
                DFS(i);

        return 0;
}

Other related posts: