admin管理员组文章数量:1622542
题目链接
#include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
char a[25];
int dist[(1<<20)];//dist表示层数,即与给出的原串的不相似度
queue<int>que;
int main() {
memset(dist,-1,sizeof(dist));//dist先全部初始化为-1,表示所有情况全部都没入过队列
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
scanf("%s",a);
int now=0;
for(int g=0;g<k;g++)
if(a[g]=='1')
now|=(1<<g);//相当于把字符串转化为数字(反向存入)
que.push(now);
dist[now]=0;
}
int ans;
while(!que.empty()) {
int K=que.front();
que.pop();
for(int i=0;i<k;i++) {
int to=K^(1<<i);//通过异或,判断出这个字符串与队首字符串的不相似度
if(dist[to]!=-1)//如果曾经访问过,不再将这个字符串压入队列(这一步实现original)
continue;
dist[to]=dist[K]+1;
// cout<<"to="<<to<<" "<<"dist[to]="<<dist[to]<<endl;
que.push(to);
ans=to;
}
}
for(int i=0;i<k;i++)
printf("%d",ans%2),ans/=2;//输出层数最大的串,即距离给出的原串差异最大(反向存入,此时要反向输出)
printf("\n");
}
本文标签: NordicCollegiatedistinctivecharacterProgramming
版权声明:本文标题:Distinctive Character --- Nordic Collegiate Programming Contest 2017(queue实现bfs) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728870711a1177244.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论