2496882_mle.cpp

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

#include <stdio.h>
#include <queue>
#include <algorithm>
#define INIT (Tree *)malloc(sizeof(Tree))
using namespace std;

int n, m, max, ans;
int p[] = {1,2,4,8,16,32,64,128};
char map[130][130];
typedef struct node
{
	int l;
	char map[130][130];
}Q;

queue <Q> que;

typedef struct Node
{
	char word[4100];
	struct Node *l, *r;
}Tree;

Tree *head;
int mark = 1;

int insert(char word[])
{
	Tree *s, *p;

	if(mark)
	{
		head = INIT;
		mark = 0;
		strcpy(head->word,word);
		head->l = head->r = NULL;
	}
	else
	{
		s = head;
		p = INIT;
		strcpy(p->word,word);
		p->l = p->r = NULL;
		while(s)
		{
			if(strcmp(s->word,word)>0)
				if(s->l)
					s = s->l;
				else
				{
					s->l = p;
					break;
				}
				else
					if(strcmp(s->word,word)<0)
						if(s->r)
							s = s->r;
						else
						{
							s->r = p;
							break;
						}
						else
						{
							return 1;
							break;
						}
		}
	}
	return 0;
}

int yes(int lr, int lc, int rr, int rc)
{
	int i, j;
	int m1, m2;

	m1 = m2 = 0;
	for(i = lr; i < rr; i++)
		for(j =lc; j < rc; j++)
		{
			if(map[i][j]=='0')
				m1 = 1;
			if(map[i][j]=='1')
				m2 = 1;
			if(m1&&m2)
				return 0;
		}
	return 1;
}

int check(int lr, int lc, int rr, int rc)
{
	int midr, midc;

	if(rr==lr-1)
		return 1;
	if(yes(lr,lc,rr,rc))
		return 1;
	midr = (lr+rr)/2;
	midc = (lc+rc)/2;
	return 1+check(lr,lc,midr,midc)+check(lr,midc,midr,rc)+check(midr,lc,rr,midc)+check(midr,midc,rr,rc);
}

int Check(char str[][130], int l)
{
	int m1, m2;
	int i, j;

	m1 = m2 = 0;
	for(i = 1; i <= l; i++)
		for(j = 1; j <= l; j++)
		{
			if(str[i][j]=='0')
				m1 = 1;
			if(str[i][j]=='1')
				m2 = 1;
			if(m1&&m2)
				return 0;
		}
	return 1;
}

void make_num(char str[],int l,char Map[][130])
{
	int i;
	char emp[4100] = "";

	for(i = 1; i <= l; i++)
		strcat(emp,&Map[i][1]);
	strcpy(str,emp);
}

void bfs()
{
	int i;
	char str[4100];
	Q tt, tmp;

	for(i = 1; i <= max; i++)
		strcpy(tt.map[i],map[i]);
	tt.l = max;
	que.push(tt);
	ans = 1;
	while(!que.empty())
	{
		tt = que.front();que.pop();
		if(tt.l==1||Check(tt.map,tt.l))
		{
			
			continue;
		}
		tmp.l = tt.l/2;
		for(i = 1; i <= tmp.l; i++)
		{
			strcpy(tmp.map[i],tt.map[i]);
			tmp.map[i][tmp.l+1] = '\0';
		}
		make_num(str,tmp.l,tmp.map);
		if(Check(tmp.map,tmp.l)||!insert(str))
		{
			ans++;
			que.push(tmp);
		}
		for(i = 1; i <= tmp.l; i++)
		{
			strcpy(&tmp.map[i][1],&tt.map[i][tmp.l+1]);
			tmp.map[i][tmp.l+1] = '\0';
		}
		make_num(str,tmp.l,tmp.map);
		if(Check(tmp.map,tmp.l)||!insert(str))
		{
			ans++;
			que.push(tmp);
		}
		for(i = 1; i <= tmp.l; i++)
		{
			strcpy(tmp.map[i],tt.map[i+tmp.l]);
			tmp.map[i][tmp.l+1] = '\0';
		}
		make_num(str,tmp.l,tmp.map);
		if(Check(tmp.map,tmp.l)||!insert(str))
		{
			ans++;
			que.push(tmp);
		}
		for(i = 1; i <= tmp.l; i++)
		{
			strcpy(&tmp.map[i][1],&tt.map[i+tmp.l][tmp.l+1]);
			tmp.map[i][tmp.l+1] = '\0';
		}
		make_num(str,tmp.l,tmp.map);
		if(Check(tmp.map,tmp.l)||!insert(str))
		{
			ans++;
			que.push(tmp);
		}
	}
}

int main()
{
	int i, j;

	while(scanf("%d%d",&n,&m)==2,m)
	{
		max = m>n?m:n;
		for(i = 0; i < 8; i++)
			if(max<=p[i])
			{
				max = p[i];
				break;
			}
		for(i = 1; i <= n; i++)
		{
			map[i][0] = '0';
			scanf("%s",&map[i][1]);
			for(j = m+1; j <= max; j++)
				map[i][j] = '0';
			map[i][j] = '\0';
		}
		for(i = n+1; i <= max; i++)
		{
			for(j = 0; j <= max; j++)
				map[i][j] = '0';
			map[i][j] = '\0';
		}
		ans = check(1,1,max+1,max+1);
		printf("%d ",ans);
		ans = 0;
		bfs();
		printf("%d\n",ans);
	}
	return 1;
}