USACO-Section 2.1 Hamming Codes (DFS)

説明

N,B,Dが与えられる:N個の符号化(1<=N<=64)が見出され、各符号化はBビット[バイナリ](1<=B<=8)であり、両符号化間に少なくともD単位の「ヘミング距離」(1<=D<=7)がある.「ヘミング距離」とは、2つの符号化について、それらのバイナリ表現における異なるバイナリビットの数を指す.次の2つの符号化0 x 554と0 x 234の違いを見てください(0 x 554は16進数を表し、各ビットはそれぞれ5,5,4です).

0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
     xxx  xx

5位が違うので「海明距離」は5です.

書式設定

PROGRAM NAME: hamming
INPUT FORMAT:
(file hamming.in)
N,B,Dを含む行.
OUTPUT FORMAT:
(file hamming.out)
N個の符号化(10進数で表す)、並べ替え、10個の1行.解が多ければ、あなたのプログラムはこのような解を出力します:もしそれを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?'
':' ');
    }
    return 0;
}