3583391_wa.cpp

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

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

using namespace std;

short map[513][513];

void solve(int a, int b, int c, int d, string str)
{
	int i, j, cnt;
	size_t st;

	if (str.at(0) != 'Q')
	{
		for (i = a; i <= c; i++)
		{
			for (j = b; j <= d; j++)
			{
				map[i][j] = (str.at(0) == 'B');
			}
		}
		return ;
	}
	str = str.substr(1);
	cnt = 0;
	for (st = 0; st < str.length(); st++)
	{
		if (str.at(st) == 'Q')
		{
			cnt -= 3;
		}
		else
		{
			cnt++;
		}
		if (cnt == 1)
		{
			solve(a, b, (c + a) / 2, (b + d) / 2, str.substr(0, st + 1));
			str = str.substr(st + 1);
			break;
		}
	}
	cnt = 0;
	for (st = 0; st < str.length(); st++)
	{
		if (str.at(st) == 'Q')
		{
			cnt -= 3;
		}
		else
		{
			cnt++;
		}
		if (cnt == 1)
		{
			solve(a, (b + d) / 2 + 1, (c + a) / 2, d, str.substr(0, st + 1));
			str = str.substr(st + 1);
			break;
		}
	}
	cnt = 0;
	for (st = 0; st < str.length(); st++)
	{
		if (str.at(st) == 'Q')
		{
			cnt -= 3;
		}
		else
		{
			cnt++;
		}
		if (cnt == 1)
		{
			solve((c + a) / 2 + 1, b, c, (b + d) / 2, str.substr(0, st + 1));
			str = str.substr(st + 1);
			break;
		}
	}
	solve((c + a) / 2 + 1, (b + d) / 2 + 1, c, d, str);
}

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(1, 1, n, 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] == 0)
				{
					tmp += v[l];
				}
			}
			printf("0x%c%c,", ch[tmp % 16], ch[tmp / 16 % 16]);
		}
		puts("");
	}
	puts("};");
	//for (i = 1; i <= n; i++)
	//	puts(&Tmp[i][1]);
	return 0;
}