狗狗40题搞完纪念 » 1004

1004
1004.cpp


#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct Wnd {
	static char buf[1024][1024];
	const char* const p;
	const char* q;
	char t[64];
	int n, l[64], r[64], w[64], h[64];

	Wnd(const char* p) : p(strdup(p)) {
	}

	~Wnd() {
		delete p;
	}

	int _relax() {
		int m = n;
		t[n++] = *q++;
		if (t[m] == '-' || t[m] == '|') {
			l[m] = _relax();
			r[m] = _relax();
			if (t[m] == '-') {
				w[m] = max(w[l[m]], w[r[m]]);
				h[m] = h[l[m]] + h[r[m]];
			} else {
				w[m] = w[l[m]] + w[r[m]];
				h[m] = max(h[l[m]], h[r[m]]);
			}
		} else {
			l[m] = r[m] = -1;
			w[m] = h[m] = 2;
		}
		return m;
	}

	void relax() {
		q = p;
		n = 0;
		_relax();
	}

	void _render(int m, int x, int y) {
		if (t[m] == '-') {
			int hh = h[l[m]] + h[r[m]];
			w[l[m]] = w[m];
			w[r[m]] = w[m];
			h[l[m]] = (h[m] * h[l[m]] + hh - 1) / hh;
			h[r[m]] = (h[m] * h[r[m]]) / hh;
			buf[x + h[l[m]]][y] = buf[x + h[l[m]]][y + w[m]] = '*';
			for (int j = 1; j < w[m]; ++j) {
				buf[x + h[l[m]]][y + j] = '-';
			}
			_render(l[m], x, y);
			_render(r[m], x + h[l[m]], y);
		} else if (t[m] == '|') {
			int ww = w[l[m]] + w[r[m]];
			w[l[m]] = (w[m] * w[l[m]] + ww - 1) / ww;
			w[r[m]] = (w[m] * w[r[m]]) / ww;
			h[l[m]] = h[m];
			h[r[m]] = h[m];
			buf[x][y + w[l[m]]] = buf[x + h[m]][y + w[l[m]]] = '*';
			for (int i = 1; i < h[m]; ++i) {
				buf[x + i][y + w[l[m]]] = '|';
			}
			_render(l[m], x, y);
			_render(r[m], x, y + w[l[m]]);
		} else {
			buf[x][y] = t[m];
		}
	}

	void render() {
		buf[0][0] = buf[0][w[0]] = buf[h[0]][0] = buf[h[0]][w[0]] = '*';
		buf[0][w[0] + 1] = buf[h[0]][w[0] + 1] = '\0';
		for (int i = 1; i < h[0]; ++i) {
			buf[i][0] = buf[i][w[0]] = '|';
			buf[i][w[0] + 1] = '\0';
		}
		for (int j = 1; j < w[0]; ++j) {
			buf[0][j] = buf[h[0]][j] = '-';
		}
		for (int i = 1; i < h[0]; ++i) {
			for (int j = 1; j < w[0]; ++j) {
				buf[i][j] = ' ';
			}
		}
		_render(0, 0, 0);
		for (int i = 0; i <= h[0]; ++i) {
			puts(buf[i]);
		}
	}
};

char Wnd::buf[1024][1024];

int main() {
	int re;
	char buf[4096];

	scanf("%d", &re);
	for (int ri = 1; ri <= re; ++ri) {
		scanf("%s", buf);
		Wnd wnd(buf);
		wnd.relax();
		printf("%d\n", ri);
		wnd.render();
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//330 	2010-06-27 21:25:32 	Accepted 	1004 	C++ 	0 	1204 	anotherpeg 	Source
One Response to “1004”
  1. [...] 然后我们实现solve函数. 同样, 我们要传一个参照坐标x, y. 然后传一个边长, 通过这三个参数, 就可以完全确定, 画出的图形在地图上的位置了. solve函数的主题, 主要是剥去边缘, 然后调用n-3, 或者n-6. n=1,2,3的构造就不说了, 之后,我们4的构造, 可以用之前的思想, 构造2的基本块, 然后分形的做. 6也是类似的. 所以这里启发我们, 为了快速做这件事, 可以写个得到2*2的4中基本块的一个类似paint的函数, 我叫做getX. 然后构造4的时候就和构造2的时候基本一样了,只不过把paint调用换成get, 然后坐标偏移都是两倍的关系. 6也可以用2的基本块, 划归到n=3的情形. 然后我们考虑大数据的边界怎么画, 就是2*3的矩形, 不断填. 所以n-3的时候是2*3的块, n-6的时候,就是两倍大的2*3块, 又可以用get函数来类似做了. 所以这个get能节省很多代码. (自己思考设计过代码, 才能发现这个). 然后左下角是个3或者6的L型. 这个可以调用solve, 所以draw和solve是相互调用的过程. 所以为了通过编译, 我们需要先写两个函数声明. 到此函数就实现完了. 扩展性也比较强. 代码包含一些注释和几个累的函数, 虽然看上去行数很多, 但是十分好写, 思路清晰. 其中必要的注释也是为了队友能看懂. 也帮助自己写代码的时候不会敲错. 对了这个x, y坐标参照的代码, 是从watashi的代码里学习的. 题目来源, LINK, Code [...]

  2.  
Leave a Reply