연습 문제 8-5 종이접기 자국(Paper Folding, UVa177)

생각:
전형적인 귀속 분형 문제.첫 번째 단계는 규칙을 찾아야 한다. 시작할 때 나는 회전하는 각도에서 생각해서 해답을 구할 수 없다.
그리고 방향표화도: r->ru->rulu...매번 증가하는 부분은 원래 부분의 역순으로 시계 반대 방향으로 90도 회전하는 것을 발견했다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define SF(a) scanf("%d", &a)
#define PF(a) printf("%d
", a)  
#define SFF(a, b) scanf("%d%d", &a, &b)  
#define SFFF(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define SFFFF(a, b, c, d) scanf("%d%d%d%d", &a, &b, &c, &d)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define IN() freopen("in.txt", "r", stdin)
#define OUT() freopen("out.txt", "w", stdout)
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define PB push_back
#define LL long long
#define mod 10007
#define inf 107
#define eps 1e-12
using namespace std;
int buf[20];
int read() {
	int x = 0; char ch = getchar(); bool f = 0;
	while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
void write(int x) {
	if (!x) { putchar(48); return; }
	int l = 0; if (x < 0) putchar('-'), x = -x;
	while (x) buf[++l] = x % 10, x = x / 10;
	while (l) putchar(buf[l--] + 48);
}
//-------------------------chc------------------------------//
//e = 0, n = 1, w = 2, s = 3;

struct Node {
	int x, y;
	int dir;
	Node(int x = 0, int y = 0, int dir = 0) : x(x), y(y), dir(dir) { }
	bool operator v;
int n;

bool cmp(Node &a, Node &b) { return a.y < b.y; }

int dx(int d1, int d2) {
	if (d1 == 1) return -1;
	else if (d2 == 3) return 1;
	else return 0;
}

int dy(int d1, int d2) {
	if (d1 == 0 || d2 == 0) return 1;
	else return -1;
}

Node NextNode(int dir, Node u) {
	int ndir = (dir+1) % 4;
	int nx = u.x + dx(u.dir, ndir), ny = u.y + dy(u.dir, ndir);
	return Node(nx, ny, ndir);
}

void solve(int d) {
	if (d >= n) return;
	Node preu = v.back();
	for (int i = SZ(v) - 1; i >= 0; --i) {
		int predir = v[i].dir;
		Node cur = NextNode(predir, preu);
		preu = cur;
		v.push_back(cur);
	}
	solve(d + 1);
}

void print() {
	sort(v.begin(), v.end(), cmp);
	int stdy = v.front().y;
	sort(v.begin(), v.end());
	FOR(i, 0, SZ(v)) {
		v[i].y -= stdy;
	}
	FOR(i, 0, SZ(v)) {
		if (i == 0 || v[i].x != v[i -1].x) {
			if(i) putchar('
');
			FOR(j, 0, v[i].y) putchar(' ');
			putchar(v[i].dir & 1 ? '|' : '_');
		}
		else {
			FOR(j, 0, v[i].y - v[i - 1].y - 1) putchar(' ');
			putchar(v[i].dir & 1 ? '|' : '_');
		}
	}
	cout << endl;
}

int main() {
	while (~SF(n) && n) {
		v.clear();
		v.push_back(Node(0, 0, 0));
		solve(0);
		print();
		puts("^");
	}
	return 0;
}

연습 문제 8-5 종이접기 자국(Paper Folding, UVa177)

좋은 웹페이지 즐겨찾기