USACO-Section 2.1 Hamming Codes （DFS）

描述

給出 N，B 和 D：找出 N 個編碼（1 <= N <= 64），每個編碼有 B 位[二進制]（1 <= B <= 8），使得兩兩編碼之間至少有 D 個機關的“海明距離”（1 <= D <= 7）。“海明距離”是指對于兩個編碼，他們的二進制表示法中的不同二進制位的數目。看下面的兩個編碼 0x554 和 0x234 之間的差別（0x554 表示一個十六進制數，每個位上分别是 5，5，4）:

0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
不同位    xxx  xx
      

因為有五個位不同，是以“海明距離”是 5。

格式

PROGRAM NAME: hamming

INPUT FORMAT:

(file hamming.in)

一行，包括 N, B, D。

OUTPUT FORMAT:

(file hamming.out)

N 個編碼（用十進制表示），要排序，十個一行。如果有多解，你的程式要輸出這樣的解：假如把它化為2進制數，它的值要最小。

SAMPLE INPUT

16 7 3      

SAMPLE OUTPUT

0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127
      

由于0是最小的數，是以0必須有，然後DFS搜尋即可，由于是從小到大枚舉，是以找到的第一個就是題目所求答案。

/*
ID: your_id_here
PROG: hamming
LANG: C++
*/
#include <cstdio>
#include <cstring>

using namespace std;

int n,b,d,ans[65],num,ready[255],rn,t,tt,tmp,mx;

bool isLegal(int x,int y) {
    x^=y,tmp=0;
    for(t=0;t<b;++t)
        if(x&(1<<t))
            ++tmp;
    return tmp>=d;
}

inline bool choose(int index) {
    for(tt=1;tt<num;++tt)//再也不敢濫用全局變量了，查錯好辛苦，我還是按規範來吧，謹慎點好
        if(!isLegal(ans[tt],ready[index]))
            return false;
    return true;
}

bool dfs(int index) {
    if(num==n)//找到結果
        return true;
    do {
        while(index<rn&&!choose(index))
            ++index;
        if(index==rn) {//無法找到答案，數字個數-1
            --num;
            return false;
        }
        ans[num++]=ready[index++];
        if(dfs(index))
            return true;
    }while(index<rn);
    --num;//無法找到答案，數字個數-1
    return false;
}

int main() {
    int i;
    freopen("hamming.in","r",stdin);
    freopen("hamming.out","w",stdout);
    while(3==scanf("%d%d%d",&n,&b,&d)) {
        ans[0]=rn=0,num=1,mx=1<<b;
        for(i=1;i<mx;++i)
            if(isLegal(0,i))
                ready[rn++]=i;
        dfs(0);
        for(--num,i=0;i<=num;++i)
            printf("%d%c",ans[i],(i+1)%10==0||i==num?'\n':' ');
    }
    return 0;
}