Cod sursa(job #759272)

Utilizator IgnitionMihai Moraru Ignition Data 17 iunie 2012 13:08:23
Problema Fractal Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.19 kb
/*
 * 034-Fractal
 * 2012-06-17
 */
#include <stdio.h>

/*
 * Find the distance along a kth order Hilbert curve from point (1, 1) to
 * point (r, c)
 */
int distance(int order, int r, int c)
{
	if(order == 1) {
		if(r == 1 && c == 1)
			return 0;
		else if(r == 2 && c == 1)
			return 1;
		else if(r == 2 && c == 2)
			return 2;
		else if(r == 1 && c == 2)
			return 3;
	}
	/*
	 * First find in which quadrant the point lies.
	 * Then translate the coordinates.
	 * Recurse.
	 */
	int N = 1<<(order); // half the size of the square side
	int newr, newc; // translated coordinates
	int offset = 0;
	if(r <= N/2) {
		if(c <= N/2) {
			newr = c;
			newc = r;
			offset = 0;
		} else {
			newr = N-c+1;
			newc = N/2-r+1;
			offset = 3*(1<<(2*(order-1)));
		}
	} else {
		if(c <= N/2) {
			newr = r-N/2;
			newc = c;
			offset = 1*(1<<(2*(order-1)));
		} else {
			newr = r-N/2;
			newc = c-N/2;
			offset = 2*(1<<(2*(order-1)));
		}
	}
	return offset+distance(order-1, newr, newc);
}

int main()
{
	freopen("fractal.in", "r", stdin);
	freopen("fractal.out", "w", stdout);

	int k; // order of Hilbert curve
	int r; // row
	int c; // column
	scanf("%d %d %d", &k, &c, &r);
	printf("%d\n", distance(k, r, c));

	return 0;
}