DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Strange Square

10.01.2007
| 2589 views |
  • submit to reddit
        For n = 8, builds
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 0
1 1 1 1 1 0 1 0
1 1 1 1 0 0 0 0
1 1 1 0 1 1 1 0
1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0

The algorithm, for a n x n matrix is:
1. Split the matrix into 4 matrices of the same size
2. Complete the top-left one with 1
3. Repeat for each of the other 3 matrices.

#include <stdio.h>
#include <stdlib.h>

int n;
int **T;

void printM() {
	int i,
		j;
	printf("\n");
	for (i = 0; i < n; ++i) {
		for (j = 0; j < n; ++j)
			printf("%d ", T[i][j]);
		printf("\n");
	}
}

void fill(int x1, int y1, int x2, int y2) {
	printf("%d %d %d %d\n", x1, y1, x2, y2);
	//getchar();
	
	if (x1 == x2) {
		//T[x1][y1] = 1;
		return;
	}
	
	int i,
		j;
	int xm = (x1 + x2) / 2;
	int ym = (y1 + y2) / 2;
	for (i = y1; i <= ym; ++i)
		for (j = x1; j <= xm; ++j)
			T[i][j] = 1;
	
	fill(x1, ym + 1, xm, y2);
	fill(xm + 1, y1, x2, ym);
	fill(xm + 1, ym + 1, x2, y2);
}

int main(int argc, char *argv[]) {
	n = 8;
	T = (int**)malloc(n * sizeof(int*));
	int i;
	for (i = 0; i < n; ++i)
		T[i] = (int*)malloc(n * sizeof(int));
	
	int j;
	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j)
			T[i][j] = 0;
	
	fill(0, 0, n - 1, n - 1);
	printM();
	
	return 0;
}