還是回溯法.
預(yù)計(jì)算兩兩之間的漢明距離，以及用一個(gè)forbidden數(shù)組記錄不可用的數(shù)，可以優(yōu)化一下計(jì)算。
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("hamming.in");
ofstream?fout("hamming.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
//兩兩之間距離
int?dist[1<<8][1<<8];
int?n,b,d;
//最大的數(shù)
int?largest;
int?forbidden[1<<8];
//用來(lái)保存一個(gè)forbidden數(shù)組
int?tmp[1<<8];
//保存解
int?result[64];
//計(jì)算n中的1的個(gè)數(shù)
int?count_bit(int?n)
{
????int?res?=?0;
????while(n!=0){
????????n&=(n-1);
????????res++;
????}
????return?res;
}
//漢明距離為兩者異或值的1的個(gè)數(shù)
int?compute_dist(int?i,int?j)
{
????return?count_bit(i^j);
}
//將所有漢明距離小于d的數(shù)forbid掉
void?add_code(int?code)
{
????forbidden[code]++;
????for(int?i=0;i<largest;++i){
????????if(dist[code][i]<d)
????????????forbidden[i]++;
????}
}
void?output()
{
????for(int?i=0;i<n;++i){
????????if(i%10==0){
????????????out<<result[i];
????????}else{
????????????out<<"?"<<result[i];
????????????if(i%10==9)
????????????????out<<endl;
????????}
????}
????if(n%10!=0)
????????out<<endl;
}
void?backtracing(int?depth,int?code)
{
????if(forbidden[code]!=0)?return;
????result[depth]=code;
????if(depth==n-1){
????????output();
????????exit(0);
????}
????memcpy(tmp,forbidden,sizeof(int)*n);
????add_code(code);
????for(int?i=0;i<largest;++i){
????????if(forbidden[i]==0&&dist[i][code]>=d){
????????????backtracing(depth+1,i);
????????}
????}
????memcpy(forbidden,tmp,sizeof(int)*n);
}
void?solve()
{
????in>>n>>b>>d;
????
????largest?=?(1<<b);
????for(int?i=0;i<largest;++i)
????????for(int?j=i+1;j<largest;++j){
????????????dist[i][j]?=?dist[j][i]?=?compute_dist(i,j);
????????}
????backtracing(0,0);
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}