Caça-Palavras

O caça-palavras é um passa-tempo popular cujo objetivo é encontrar certas palavras em um diagrama. Nesta tarefa, iremos implementar um programa que resolve um caça-palavras. As palavras estão escondidas em uma matriz de letras e podem estar na vertical, horizontal, ou diagonal. E além disso, as palavras podem aparecer tanto em ordem direta quanto na ordem invertida!

Entrada

A entrada consiste de

• uma linha com dois inteiros m e n que correspondem ao número de linhas e de colunas da matriz
• as m linhas seguintes contém n letras cada uma, separadas por espaço
• a próxima linha contém um número p de palavras
• as p linhas seguintes contêm uma palavra em cada linha

Exemplo:

3 8
v e d j n a e o
i p y t h o n u
s u e w e t a e
1
python

Saída

A saída é parecida com a matriz de entrada, mas contém o caractere '.' nas posições em que não foi encontrada uma palavra.

. . . . . . . .
. p y t h o n .
. . . . . . . .

Implementando

Assim como nas tarefas anteriores, temos que realizar diversas atividades para completar essa tarefa:

• ler matriz, procurar diagonal, procura horizontal, procurar horizontal invertida, imprimir matriz com '.' onde não há palavra,….

Mas tudo ainda está muito confuso! Dessa vez, o problema parece um pouco mais difícil de ser resolvido. Só fazer uma lista de atividades não vai ser suficiente. Temos que ter certeza de que sabemos resolver o problema. É por isso que é importante escrevemos um algoritmo em alto nível. Antes de começar a programar, sempre escreva um algoritmo em português (ou em pseudocódigo) e verifique se ele está correto. Para essa tarefa do caça-palavras, eu escreveria algo como:

Resolver Caça-Palavras:

1. m, n = leia as dimensões da matriz
2. A = leia a matriz de caracteres de dimensões m x n
3. B = crie uma matriz de caracteres contendo '.' de dimensões m x n
4. p = leia o número de palavras a serem buscadas
5. repita p vezes:
   1. palavra = leia a palavra correspondente
   2. procure as ocorrências de palavra em A e copie os caracteres para B
   3. inverso = copie o inverso de palavra
   4. procure as ocorrências de inverso em A e copie os caracteres para B
6. escreva a matriz B na tela

Bem melhor! Agora as coisas parecem fazer sentido. Ter uma sequência de passos lógica nos permite pensar e trabalhar em cada passo separadamente, sem se preocupar com as inúmeras outras atividades com que ainda teremos que lidar.

Mas será que já temos certeza de sabemos resolver o caça palavras? Você deve se lembrar das primeiras aulas de programação, quando você aprendeu que “Um algoritmo é uma sequência de instruções bem definidas que resolvem um determinado problema.” Uma instrução ser bem definida significa que sabemos cumpri-la, ou, em nosso caso, significa que sabemos implementá-la em uma linguagem de programação inambígua. Com exceção das instruções 5.2 e 5.4, que vamos deixar para mais tarde, você já sabe implementar todas as outras instruções, pelo menos em Python. Vamos nos concentrar então em implementar cada uma dessas instruções mais simples, mas agora em C.

Lendo e criando matrizes de caracteres

Para criar uma matriz em Python podemos usar uma lista de listas.

def ler_matriz(m, n):
    matriz = []
    for i in range(m):
        # adiciona uma nova linha à matriz
        matriz.append([])

        # lê cada letra da linha atual
        for letra in input().split():
            # adiciona uma letra a linha i
            matriz[i].append(letra)

    return matriz

Em C, para representar uma matriz, usamos um vetor de vetores. Cada elemento do vetor corresponderá a uma linha e cada elemento de uma linha corresponderá a um caractere. Como todos os vetores devem ter um tamanho máximo conhecido em tempo de compilação, devemos estimar o número máximo de linhas, MAX_ALTURA, e o número máximo de caracteres por linha, MAX_LARGURA. Também como os vetores, para devolver uma matriz, devemos passá-la por parâmetro.

void ler_matriz(char matriz[MAX_ALTURA][MAX_LARGURA], int m, int n) {
    int i, j;
    char letra;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            scanf(" %c", &letra);
            matriz[i][j] = letra;
        }
    }
}

O motivo pelo qual não precisamos nos preocupar em separar os vários caracteres de uma linha na versão em C de ler_matriz, enquando em Python tivemos que usar split(), é que podemos instruir scanf a ignorar os espaços em branco ao ler um caractere, por isso usamos um espaço antes de %c.

Repare que podemos escrever uma função criar_matriz_ponto que devolve uma matriz com . em cada posição de maneira similar, mas fazendo matriz[i][j] = '.' ao invés de atribuir uma letra lida do teclado. Similarmente, também podemos escrever uma função imprimir_matriz que mostra a matriz na tela, bastando usar printf("%c ", matriz[i][i]);. Repare que você também deverá adicionar printf("\n") depois de imprimir cada linha.

Criando o programa principal

Nesse ponto, já podemos escrever toda a estrutura do nosso algoritmo para resolver caça-palavras. Ainda não sabemos implementar os passos 5.2 do algoritmo, mas sabemos que cada um desses passos deve receber uma string palavra, as matrizes A e B e as dimensões m e n. Como tudo o que precisamos para chamar uma função é saber quais os parâmetros a função recebe, podemos fingir que existe uma função marcar_ocorrencias e escrever o código da função main como se marcar_ocorrencias já fizesse o que queremos. Para poder chamar uma função, precisamos defini-la antes, então por enquanto só vamos criar uma função que recebe esses parâmetros, mas que não faz nada: isso é o que chamamos de stub.

#include <stdio.h>

#define MAX_PALAVRA  15

#define MAX_ALTURA  15
#define MAX_LARGURA 10

/* ...outras funções... */

void marcar_ocorrencias(char palavra[],
        char A[MAX_ALTURA][MAX_LARGURA],
        char B[MAX_ALTURA][MAX_LARGURA],
        int m, int n)
{ /* essa função é só um stub */ }

int main() {
    int i;
    int m, n, p;
    char A[MAX_ALTURA][MAX_LARGURA];
    char B[MAX_ALTURA][MAX_LARGURA];
    char palavra[MAX_PALAVRA], inverso[MAX_PALAVRA];

    /* lê e cria matrizes */
    scanf("%d %d", &m, &n);
    ler_matriz(A, m, n);
    criar_matriz_ponto(B, m, n);

    /* lê e marca cada palavra */
    scanf("%d", &p);
    for (i = 0; i < p; i++) {
        scanf("%s", palavra);
        marcar_ocorrencias(palavra, A, B, m, n);
        copiar_inverso(palavra, inverso);
        marcar_ocorrencias(inverso, A, B, m, n);
    }

    /* imprime matriz resultante */
    imprimir_matriz(B, m, n);
}

Resolvendo o exercício

Para terminar o nosso programa, precisamos explicar como executar as instruções 5.2 e 5.4, isso é, como implementar a função marcar_ocorrencias. Do jeito que está escrito em nosso algoritmo, essas instruções não estão bem definidas, porque elas só descrevem o que queremos, mas não explica como. No entanto conhecemos tudo de que nossa função recebe como entrada (uma string palavra, as matrizes A e B e as dimensões m e n) e sabemos tudo o que ela deve produzir como saída (alterar a matriz B de forma a copiar as ocorrências de palavra). Em outras palavras, a função marcar_ocorrencias resolve um problema menor, mas que é parte nosso problema original. Isso é o que chamamos de subproblema.

Lembrando: antes de começar a programar, devemos escrever um algoritmo que resolve o problema, então lá vai:

Marcar ocorrências(palavra, A, B, m, n):

1. Para cada linha i da matriz
   1. Para cada coluna j da linha i
      1. procurar ocorrências de palavra horizontalmente em A a partir da posição i,j e copiar letras correspondentes para matriz B
      2. procurar ocorrências verticalmente
      3. procurar ocorrências diagonalmente

De novo, quebramos o problema em subproblemas menores, cada vez mais fáceis de serem resolvidos. Além das palavra e das matrizes, o passo 1.1.1 do algoritmo acima deve receber a linha i e a coluna j da posição em que estamos procurando uma palavra. A mesma coisa vale para os passos 1.1.2 e 1.1.3. Para praticar, vamos usar a estratégia de criar stubs mais uma vez.

void marcar_ocorrencia_horizontal(char palavra[],
        char A[MAX_ALTURA][MAX_LARGURA],
        char B[MAX_ALTURA][MAX_LARGURA],
        int m, int n, int i, int j)
{ /* essa função é só um stub */ }

void marcar_ocorrencias(char palavra[],
        char A[MAX_ALTURA][MAX_LARGURA],
        char B[MAX_ALTURA][MAX_LARGURA],
        int m, int n)
{
    int i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            marcar_ocorrencia_horizontal(palavra, A, B, m, n, i, j);
            marcar_ocorrencia_vertical(palavra, A, B, m, n, i, j);
            marcar_ocorrencia_diagonal(palavra, A, B, m, n, i, j);
        }
    }
}

Finalmente, você deve descobrir como implementar marcar_ocorrencia_horizontal, marcar_ocorrencia_vertical e marcar_ocorrencia_diagonal. Para cada uma delas:

1. faça um pequeno algoritmo para resolver o problema; certifique-se de que cada instrução de seu algoritmo esteja bem definida e que você saiba implementá-la em uma linguagem de programação
2. simule cada passo de seu algoritmo com alguns caça-palavras bem pequenos até estar seguro de que o algoritmo está correto
3. se encontrar um erro, corrija seu algoritmo e verifique novamente

Depois de ter certeza de que seu algoritmo está correto, você deve implementá-lo na linguagem de programação C. Você pode começar com o código acima clicando em Caça-Palavras, preenchendo os stubs e escrevendo as funções que faltam.

Exemplos relacionados

Uma forma de arte digital é escrever textos que tenham alguma forma ou significado especial. O código abaixo escreve uma palavra várias vezes em uma matriz, cada vez mais à direita.

#include <stdio.h>
#include <string.h>

#define MAX 100

void limpar_matriz(char A[MAX][MAX], int m, int n) {
    int i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++)  {
            A[i][j] = ' ';
        }
    }
}

void imprimir_matriz(char A[MAX][MAX], int m, int n) {
    int i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++)  {
            printf("%c ", A[i][j]);
        }
        printf("\n");
    }
}

void formar_arte(char palavra[], char A[MAX][MAX], int m, int n) {
    int i, j, k;
    int tam = strlen(palavra);
    for (i = 0; i < m; i++) {
        for (j = i, k = 0; j < n && k <tam; j++, k++) {
            A[i][j] = palavra[k];
        }
    }
}

int main() {
    int m, n;
    char A[MAX][MAX];
    char palavra[MAX];
    scanf("%d %d %s", &m, &n, palavra);
    limpar_matriz(A, m, n);
    formar_arte(palavra, A, m, n);
    imprimir_matriz(A, m, n);
}

Se dermos a entrada 5 8 amargorp para esse programa ele irar gerar

a m a r g o r p
  a m a r g o r
    a m a r g o
      a m a r g
        a m a r

← Anterior Voltar