3583805_pe.cc

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

#include <string>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

short map[513][513];

struct node
{
	int a, b, c, d, f, t;
};

queue <node> q;

void solve(int n, string str)
{
	int i, j, cnt, Q;
	int a, b, c, d, f, t;

	node nd;

	nd.a = 1;nd.b = 1;
	nd.c = n;nd.d = n;
	nd.f = 0;nd.t = str.length() - 1;
	q.push(nd);
	while (!q.empty())
	{
		nd = q.front();
		q.pop();
		a = nd.a;b = nd.b;
		c = nd.c;d = nd.d;
		f = nd.f;t = nd.t;
		if (str.at(f) != 'Q')
		{
			for (i = a; i <= c; i++)
			{
				for (j = b; j <= d; j++)
				{
					map[i][j] = (str.at(f) == 'B');
				}
			}
			continue;
		}
		f++;
		cnt = 0;
		Q = 0;
		for (i = f; i <= t; i++)
		{
			if (str.at(i) == 'Q')
			{
				Q++;
			}
			else
			{
				cnt++;
			}
			if (cnt == Q * 3 + 1)
			{
				nd.a = a;nd.b = b;
				nd.c = (a + c) / 2;
				nd.d = (b + d) / 2;
				nd.f = f;
				nd.t = i;
				f = i + 1;
				q.push(nd);
				break;
			}
		}
		cnt = 0;
		Q = 0;
		for (i = f; i <= t; i++)
		{
			if (str.at(i) == 'Q')
			{
				Q++;
			}
			else
			{
				cnt++;
			}
			if (cnt == Q * 3 + 1)
			{
				nd.a = a;nd.d = d;
				nd.b = (b + d) / 2 + 1;
				nd.c = (a + c) / 2;
				nd.f = f;
				nd.t = i;
				f = i + 1;
				q.push(nd);
				break;
			}
		}
		cnt = 0;
		Q = 0;
		for (i = f; i <= t; i++)
		{
			if (str.at(i) == 'Q')
			{
				Q++;
			}
			else
			{
				cnt++;
			}
			if (cnt == Q * 3 + 1)
			{
				nd.b = b;nd.c = c;
				nd.a = (c + a) / 2 + 1;
				nd.d = (b + d) / 2;
				nd.f = f;
				nd.t = i;
				f = i + 1;
				q.push(nd);
				break;
			}
		}
		nd.d = d;nd.c = c;
		nd.a = (c + a) / 2 + 1;
		nd.b = (b + d) / 2 + 1;
		nd.f = f;
		nd.t = t;
		q.push(nd);
	}

}

int v[] = {0, 1, 2, 4, 8, 16, 32, 64, 128};
char ch[] = "0123456789abcdef";

int main()
{
	int i, j, k, n, l, tmp;
	string str;

	cin >> n >> str;
	solve(n, str);
	cout << "#define quadtree_width " << n << endl;
	cout << "#define quadtree_height  " << n << endl;
	cout << "static char quadtree_bits[] = {" << endl;
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j += 8)
		{
			tmp = 0;
			for (k = j, l = 1; k < j + 8; l++, k++)
			{
				if (map[i][k] == 1)
				{
					tmp += v[l];
				}
			}
			printf("0x%c%c,", ch[tmp / 16 % 16], ch[tmp % 16]);
		}
		puts(" ");
	}
	puts("};");
	//for (i = 1; i <= n; i++)
	//	puts(&Tmp[i][1]);
	return 0;
}