#include <cstdio>
#include <cstdlib>
#include <ctime>
#define CEL 5
#define BOR 1
#define setwall(b) setpixel(b, 0x00, 0x00, 0x00)

int H, W, S;
const int dir[4][2] =	{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
const bool	SS[7][7] =	{{0, 0, 0, 0, 0, 0, 0},
						 {0, 1, 1, 1, 1, 1, 0},
						 {0, 1, 0, 0, 0, 0, 0},
						 {0, 1, 1, 1, 1, 1, 0},
						 {0, 0, 0, 0, 0, 1, 0},
						 {0, 1, 1, 1, 1, 1, 0},
						 {0, 0, 0, 0, 0, 0, 0}},
			EE[7][7] =	{{0, 0, 0, 0, 0, 0 ,0},
						 {0, 1, 1, 1, 1, 1, 0},
						 {0, 1, 0, 0, 0, 0, 0},
						 {0, 1, 1, 1, 1, 1, 0},
						 {0, 1, 0, 0, 0, 0, 0},
						 {0, 1, 1, 1, 1, 1, 0},
						 {0, 0, 0, 0, 0, 0, 0}};
bool **chk;
char *BMP;
union QBYTE {
	char byte[4];
	short dbyte[2];
	int qbyte;
};
struct mazetype {
	QBYTE d;
	mazetype() {}
	mazetype(bool n, bool e, bool s, bool w) {
		d.byte[0] = n, d.byte[1] = e, d.byte[2] = s, d.byte[3] = w;
	}
} **M;

void exit_error(const char str[] = "Error! exiting...") {
	puts(str);
	exit(1);
}

void input() {
	puts("Make Maze!");
	printf("width height seed: ");
	if(scanf("%d%d%d", &W, &H, &S) == EOF) exit_error();
	if(H < 5 || W < 5) exit_error("size too small");
	if(H * W > 50000) exit_error("size too big");
	if(S == 0) S = time(0);
	srand(S);
}

void makemaze(int h, int w) {
	chk[h][w] = 1;
	int i, j;
	for(i = 0;; i++) {
		for(j = 0; j < 4; j++) {
			if(!chk[h + dir[j][0]][w + dir[j][1]]) break;
		}
		if(j >= 4) break;
		int d = rand() % 4;
		int nh = h + dir[d][0], nw = w + dir[d][1];
		if(chk[nh][nw]) continue;
		M[h][w].d.byte[d] = 0, M[nh][nw].d.byte[(d + 2) % 4] = 0;
		makemaze(nh, nw);
	}
}

void setpixel(char *start, char r, char g, char b) {
	*start = b, *(start + 1) = g, *(start + 2) = r;
}

void printheader(int bitmapsize, int width, int height) {
	unsigned int i;
	char head1[] = {0x42, 0x4d};
	char head3[] = {0, 0, 0, 0, 0x36, 0, 0, 0};
	char head4[] = {0x28, 0, 0, 0};
	char head7[] = {0x01, 0, 0x18, 0, 0, 0, 0, 0};
	char head9[] = {0x13, 0x0b, 0, 0, 0x13, 0x0b, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
	QBYTE head2, head5, head6, head8;
	head2.qbyte = bitmapsize + 54;
	head5.qbyte = width;
	head6.qbyte = -height;
	head8.qbyte = bitmapsize;
	for(i = 0; i < sizeof head1; i++) putchar(head1[i]);
	for(i = 0; i < sizeof head2.byte; i++) putchar(head2.byte[i]);
	for(i = 0; i < sizeof head3; i++) putchar(head3[i]);
	for(i = 0; i < sizeof head4; i++) putchar(head4[i]);
	for(i = 0; i < sizeof head5.byte; i++) putchar(head5.byte[i]);
	for(i = 0; i < sizeof head6.byte; i++) putchar(head6.byte[i]);
	for(i = 0; i < sizeof head7; i++) putchar(head7[i]);
	for(i = 0; i < sizeof head8.byte; i++) putchar(head8.byte[i]);
	for(i = 0; i < sizeof head9; i++) putchar(head9[i]);
}

int main() {
	// input
	input();
	// make maze
	int i, j;
	M = new mazetype*[H + 2];
	chk = new bool*[H + 2];
	for(i = 0; i < H + 2; i++) {
		M[i] = new mazetype[W + 2];
		chk[i] = new bool[W + 2];
		for(j = 0; j < W + 2; j++) {
			M[i][j] = mazetype(1, 1, 1, 1);
			if(i == 0 || i == H + 1 || j == 0 || j == W + 1) chk[i][j] = 1;
			else chk[i][j] = 0;
		}
	}
	makemaze(1, 1);
	// print bitmap header
	if(freopen("maze.bmp", "w", stdout) == NULL) exit_error("Cannot open output file");
	int bmpw = W * (CEL + BOR * 2) * 3, bmph = H * (CEL + BOR * 2), pxw = W * (CEL + BOR * 2);
	bmpw = bmpw % 4? (bmpw / 4 + 1) * 4: bmpw;
	BMP = new char[bmpw * bmph];
	for(i = 0; i < bmph * bmpw; i += 3) setpixel(&BMP[i], 0xFF, 0xFF, 0xDD);
	printheader(bmpw * bmph, W * (CEL + BOR * 2), H * (CEL + BOR * 2));
	// print maze
	for(i = 0; i < bmph; i++) {
		for(j = 0; j < pxw; j++) {
			int vp = i % (CEL + BOR * 2), hp = j % (CEL + BOR * 2);
			int hc = i / (CEL + BOR * 2) + 1, wc = j / (CEL + BOR * 2) + 1;
			if(vp < BOR) {
				if(hp < BOR || hp > CEL + BOR - 1) setwall(&BMP[i * bmpw + j * 3]);
				else if(M[hc][wc].d.byte[0]) setwall(&BMP[i * bmpw + j * 3]);
			} else if(vp > CEL + BOR - 1) {
				if(hp < BOR || hp > CEL + BOR - 1) setwall(&BMP[i * bmpw + j * 3]);
				else if(M[hc][wc].d.byte[2]) setwall(&BMP[i * bmpw + j * 3]);
			} else {
				if(hp < BOR && M[hc][wc].d.byte[3]) setwall(&BMP[i * bmpw + j * 3]);
				else if(hp > CEL + BOR - 1 && M[hc][wc].d.byte[1]) setwall(&BMP[i * bmpw + j * 3]);
			}
		}
	}
	for(i = 0; i < 7; i++) {
		for(j = 0; j < 7; j++)
			if(SS[i][j]) setpixel(&BMP[i * bmpw + j * 3], 0xff, 0x11, 0x11);
	}
	int endh = (H - 1) * (CEL + BOR * 2), endw = (W - 1) * (CEL + BOR * 2);
	for(i = endh; i < bmph; i++) {
		for(j = endw; j < pxw; j++)
			if(EE[i - endh][j - endw]) setpixel(&BMP[i * bmpw + j * 3], 0x11, 0x11, 0xff);
	}
	for(i = 0; i < bmpw * bmph; i++) putchar(BMP[i]);
	return 0;
}