hdu 4712 Hamming Distance bfs

时间:2022-06-15 10:29:22

我的做法,多次宽搜,因为后面的搜索扩展的节点会比较少,所以复杂度还是不需要太悲观的,然后加上一开始对答案的估计,用估计值来剪枝,就可以ac了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char a[11];
int key[111111];
int hash[1111111];
int que[2111111];
int front,end;
int ans;
void bfs()
{
while(front<=end)
{
int now=que[front++];
if(hash[now]>=ans) continue;
for(int i=0;i<=19;i++)
{
int to=(now^(1<<i));
if(hash[to]>hash[now]+1)
{
hash[to]=hash[now]+1;
que[++end]=to;
}
}
}
} int cal(int t,int s)
{
int sum=0;
for(int i=0;i<=19;i++)
{
int tmp=key[t]&(1<<i);
int txt=key[s]&(1<<i);
if(tmp^txt)
sum++;
}
return sum;
} int main()
{
// freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
memset(hash,1,sizeof(hash));
ans=33;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=5;j++)
{
scanf("%c",&a[j]);
if(a[j]==' '||a[j]=='\n')
j--;
}
int txt=1,sum=0;
for(int j=1;j<=5;j++)
{
if(a[j]>='0'&&a[j]<='9')
sum+=(a[j]-'0')*txt;
else
sum+=(a[j]-'A'+10)*txt;
txt*=16;
}
key[i]=sum;
}
sort(key+1,key+1+n);
for(int i=1;i<n;i++)
ans=min(ans,cal(i,i+1)); for(int i=1;i<=n;i++)
{
ans=min(ans,hash[key[i]]);
front=1,end=0;
que[++end]=key[i];
hash[key[i]]=0;
bfs();
} cout<<ans<<endl;
}
return 0;
}