Photolog

Through the Looking-Glass
2010-10-12: Through the Looking-Glass
My radio speaks is binary!
2010-10-10: My radio speaks is binary!
Gigaminx: (present for my birthday)
2010-09-16: Gigaminx: (present for my birthday)
Trini on bike
2010-09-05: Trini on bike
Valporquero
2010-08-28: Valporquero
My new bike!
2010-08-22: My new bike!
Mario and Ana's wedding
2010-08-13: Mario and Ana's wedding
Canyoning in Guara
2010-08-07: Canyoning in Guara
Trini and Mari in Marbella
2010-08-05: Trini and Mari in Marbella
Trini and Chelo in Tabarca
2010-08-03: Trini and Chelo in Tabarca
Valid XHTML 1.1
Log in
Back to list of problems

Squares

201.c

/* 201 - Squares */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n;
char right[20][20];
char down[20][20];

void
calc(void) {
	int z;
	int i,j,k;
	int nosquares=1;

	for (z=1; z<=n-1; z++) {
		int squares=0;
		for (i=1; i<=n-z; i++) {
			for (j=1; j<=n-z; j++) {
				for (k=0; k<z; k++) {
					if (!right[i][j+k]) {
#if DEBUG
						printf("z=%d i=%d j=%d OUT: right[%d][%d]=%d\n", z, i, j, i, j+k, right[i][j+k]);
#endif
						goto out;
					}
					if (!right[i+z][j+k]) {
#if DEBUG
						printf("z=%d i=%d j=%d OUT: right[%d][%d]=%d\n", z, i, j, i+z, j+k, right[i+z][j+k]);
#endif
						goto out;
					}
				}
				for (k=0; k<z; k++) {
					if (!down[j][i+k]) {
#if DEBUG
						printf("z=%d i=%d j=%d OUT: down[%d][%d]=%d\n", z, i, j, j, i+k, down[j][i+k]);
#endif
						goto out;
					}
					if (!down[j+z][i+k]) {
#if DEBUG
						printf("z=%d i=%d j=%d OUT: down[%d][%d]=%d\n", z, i, j, j+z, i+k, down[j+z][i+k]);
#endif
						goto out;
					}
				}
				squares++;
#if DEBUG
				printf("found square: z=%d, i=%d, j=%d\n", z, i, j);
#endif
out:
			;
			}
		}
		if (squares) {
			printf("%d square (s) of size %d\n", squares, z);
			nosquares=0;
		}
	}
	if (nosquares) {
		printf("No completed squares can be found.\n");
	}
}

int
main(void) {
	int m;
	int i;
	int problem=1;

	while (1) {
		memset(right, 0, sizeof(right));
		memset(down, 0, sizeof(down));

		if (scanf("%d %d", &n, &m) != 2) {
			break;
		}
		for (i=0; i<m; i++) {
			int a,b;
			char c;
			scanf(" %c %d %d", &c, &a, &b);
			if (c=='H') {
				right[a][b]=1;
			} else {
				down[a][b]=1;
			}
		}
		if (problem>1) {
			printf("\n**********************************\n\n");
		}
		printf("Problem #%d\n\n", problem++);
		calc();
	}
	return 0;
}