2983300_ac_0ms_264k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

char str[10001][16];

int main()
{
	int n, g, ans;
	int t, i, m, j, no, s;
	int mark[10001], num[16];

	scanf("%d",&t);
	while(t--)
	{
		s = 0;
		scanf("%d%d",&n,&g);
		for(i = 0; i < n; i++)
			scanf("%s",str[i]);
		ans = 0;
		if(n==1)
		{
			puts("0");
			continue;
		}
		memset(mark,0,sizeof(mark));
		no = n;
		while(1)
		{
			memset(num,0,sizeof(num));
			for(i = 0; i < n; i++)
			{
				if(mark[i]==0)
				{
					for(j = 0; j < g; j++)
					{
						num[j] += str[i][j]-'0';
					}
				}
			}
			for(i = 0; i < g; i++)
				if(str[0][i] == '0')
					num[i] = no-num[i];
			m = 0;
			for(i = 1; i < g; i++)
				if(num[i] < num[m])
					m = i;
			if(str[0][m]=='0')
				s++;
			for(i = 0; i < n; i++)
			{
				if(mark[i]==0&&str[i][m]!=str[0][m])
				{
					mark[i] = 1;
				}
			}
			ans++;
			no = 0;
			for(i = 0; i < n; i++)
				if(mark[i]==0)
					no++;
			if(no==1)
				break;
		}
		printf("%d\n",ans+(s>2));
	}
	return 0;
}