Palavras Cruzadas (OBI99)

Acabei de resolver o problema Palavras Cruzadas; até agora foi o mais difícil da OBI 1999 (ainda que fácil se comparado a problemas de outras OBIs mais recentes, como Rede Ótica e Orkut):

Palavras Cruzadas

O conhecido passatempo de palavras cruzadas é composto por uma grade retangular de quadrados branos e pretos e duas listas de definições. Uma das listas de definições é para palavras escritas da esquerda para a direita nos quadrados brancos (nas linhas) e a outra lista é para palavras que devem ser escritas de cima para baixo nos quadrados brancos (nas colunas). Uma palavra é uma sequência de dois ou mais caracteres do alfabeto. para resolver um jogo de palavras cruzadas, as palavras correspondentes às definições devem ser escritas nos quadrados brancos da grade.

[…]

Tarefa

Sua tarefa é escrever um programa que recebe como entrada vários jogos de palavras cruzadas resolvidas e produz as listas de palavras verticais e horizontais que constituem as soluções.

Na outra vez que eu tinha tentado fazer foi difícil, mas dessa vez foi tranquilo. Bom… O algoritmo tá bem simples e já coloquei na seção de scripts. Gostei do programa, a saída é bem bonita. :lol:

//Palavras Cruzadas - OBI1999

#include <stdio.h>
#define NMAX 102

int nu[NMAX][NMAX], proximonumero;
char mt[NMAX][NMAX];

int numera(i, j) {
	if (!nu[i][j]) {
		nu[i][j]=proximonumero++;
		//printf("É numerada a coordenada %d %d com %d.\n", i, j, nu[i][j]);
	}
}

int main() {
	int n, m, i, j, k, teste=1, vertical, horizontal;
	char enter;

	while (scanf("%d %d", &n, &m)&&n) {
		//imprime o número do teste
		printf("Teste %d\n", teste++);
		//zera as matrizes
		for (i=0; i<=n+1; i++) {
			for (j=0; j<=m+1; j++) {
				mt[i][j]='*';
				nu[i][j]=0;
			}
		}
		//pega o enter
		scanf("%c", &enter);
		//pega os chars e coloca na matriz
		for (i=1; i<=n; i++) {
			for (j=1; j<=m; j++) {
				scanf("%c", &mt[i][j]);
			}
			scanf("%c", &enter);
		}
		//define o proximo numero pra 1
		proximonumero=1;
		vertical=0;
		horizontal=0;
		//numera a matriz
		for (i=1; i<=n; i++) {
			for (j=1; j<=m; j++) {
				if (mt[i][j]!='*') {
					if (mt[i][j-1]=='*'&&mt[i][j+1]!='*') {
						numera(i, j);
						horizontal=1;
					}
					if (mt[i-1][j]=='*'&&mt[i+1][j]!='*') {
						numera(i, j);
						vertical=1;
					}
				}
			}
		}
		//imprime palavras horizontais
		if (horizontal) {
			printf("Horizontais:\n");
			for (i=1; i<=n; i++) {
				for (j=1; j<=m; j++) {
					if (mt[i][j]!='*'&&mt[i][j-1]=='*'&&mt[i][j+1]!='*') {
						printf("  %d. ", nu[i][j]);
						for (k=j; mt[i][k]!='*'; k++) {
						       printf("%c", mt[i][k]);
						}
				 		printf("\n");
					}
				}
			}
		}

		//imprime palavras verticais
		if (vertical) {
			printf("Verticais:\n");
			for (i=1; i<=n; i++) {
				for (j=1; j<=m; j++) {
					if (mt[i][j]!='*'&&mt[i-1][j]=='*'&&mt[i+1][j]!='*') {
					       printf("  %d. ", nu[i][j]);
					       for (k=i; mt[k][j]!='*'; k++) {
						       printf("%c", mt[k][j]);
					       }
					       printf("\n");
					}
				}
			}
		}

		//enter
		printf("\n");
	}
}

Estive utilizando o screen e Lynx, Tmsnc, etc. por um tempo. É muito bom, bastante leve. É uma ótima opção para computadores lentos ou pra quem não quer perder tempo abrindo modo gráfico (se bem que se for pra ir na internet, ainda vale mais a pena abrir um Fluxbox ou algo do tipo). Bom… Uma vantagem também é já usar Mutt e Tmsnc normalmente. Aliás, o TMSNC tá muito bom! Saiu essa semana o 0.2.0b com algumas novidades legais como sons de login, mensagens, etc.

Já passou uma semana de aula… É meio corrido e não dá muito tempo pra programar, mas acabo estudando TeX durante a aula para escrever os cadernos. O treino de vôlei vai começar esta semana e ainda não falei com o Vavá sobre o treino para as olimpíadas de matemática.

Consegui convencer dois amigos a usarem Firefox mostrando o meu post sobre o Fotolog.net e espero que este artigo da falha ajude a mostrar para as pessoas que o Internet Explorer é muito vulnerável. Já enviei também um e-mail ao administrador do Fotolog.net falando do bug.

No mais, nada…

© 2005–2020 Tiago Madeira