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