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://m.elefans.com/dianzi/1728870711a1177244.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。