Escreva um programa que recebe uma matriz de caracteres (letras ou números) e uma palavra e determina se esta palavra está na matriz. Uma palavra está em uma matriz se sua sequência de letras pode ser encontrada na matriz, de tal maneira que:
  • a primeira letra da palavra existe na matriz e
  • o restante da palavra está disposto em uma reta que se inicia na posição da primeira letra e segue em um dos oito sentidos diferentes (N, NE, L, SE, S, SO, O, NO);
Seu programa deve imprimir todas as posições iniciais em que a palavra pode ser encontrada na matriz (caso exista alguma).
Por exemplo, para a matriz 6 \times 3
\left[\begin{array}{cccccc} 1 & 2 & 3 & 4 & T & R \\\ A & S & A & C & R & T \\\\ 0 & X & G & T & B & K \end{array}\right]
e a palavra “CASA”, seu programa deve imprimir a posição (1,3).
Lembre-se de que seu programa deve também ler o tamanho das dimensões da matriz. Assuma que o número de linhas e colunas desta matriz é sempre menor ou igual a 10 .

Passo 1

O que o problema pede (em palavras claras):
  • Receber uma matriz de caracteres com R linhas e C colunas (ambos \le 10).
  • Receber uma palavra (sequência de caracteres).
  • Determinar todas as posições iniciais na matriz onde a palavra aparece inteira, seguindo uma reta em um dos oito sentidos: Norte, Nordeste, Leste, Sudeste, Sul, Sudoeste, Oeste, Noroeste. A primeira letra da palavra deve coincidir com a célula inicial; as letras seguintes seguem na direção escolhida sem “pulos”.
  • Imprimir todas as posições iniciais encontradas (se houver).
Informações que temos/assumimos do enunciado:
  • As entradas incluem o tamanho da matriz (linhas R e colunas C), os elementos da matriz (caracteres, podem ser letras ou dígitos) e a palavra a buscar.
  • A saída deve listar as posições iniciais. No exemplo dado a saída foi (1,3). Vou adotar o mesmo sistema de índices que o exemplo usa: índices zero-based, isto é, a primeira linha é 0 e a primeira coluna é 0. (Assim, o exemplo tem início em linha 1, coluna 3.)
  • Deve-se considerar direções retilíneas entre vizinhos (vizinhos de 8-direções), sem saltos e sem “dobrar” a trajetória.

Passo 2

Ideia do método (explicação didática e passo-a-passo do raciocínio):
  • Estratégia direta e segura: percorrer todas as células da matriz; para cada célula que tenha a mesma letra da primeira letra da palavra, testar as oito direções e verificar se, seguindo essa direção, todas as letras da palavra coincidem com as células da matriz e permanecem dentro dos limites.
  • Por que isso funciona? Porque qualquer ocorrência da palavra começa em alguma célula e segue uma das oito direções fixas; testar todas as células como possíveis inícios e todas as direções garante que nenhuma ocorrência seja perdida.
  • Complexidade: se R é número de linhas e C o número de colunas e L o comprimento da palavra, o algoritmo tenta até R\cdot C pontos iniciais e até 8 direções para cada um, e para cada tentativa compara até L caracteres. Logo, custo no pior caso é O(8 \cdot R \cdot C \cdot L), que é perfeitamente aceitável com R,C \le 10.

Passo 3

Definição das direções e como representá-las (já prontas para implementar):
  • Representar cada direção por um par de deslocamentos na linha e na coluna: (\Delta r, \Delta c).
  • Usaremos a convenção de índices de linha/coluna: linha aumenta para baixo, coluna aumenta para a direita. Então as oito direções (N, NE, L, SE, S, SO, O, NO) são, respectivamente:
(-1,0),\;(-1,1),\;(0,1),\;(1,1),\;(1,0),\;(1,-1),\;(0,-1),\;(-1,-1).
  • Explicação: por exemplo, (-1,0) significa mover uma linha para cima (Norte) sem mudar coluna; (0,1) significa mover para a direita (Leste); (1,1) é diagonal para baixo e direita (Sudeste), etc.

Passo 4

Como testar uma direção a partir de uma célula inicial (i,j) (passo-a-passo operacional):
  1. Seja L o comprimento da palavra. Para cada k de 0 até L-1 calcule a posição da k-ésima letra como
r = i + k\cdot\Delta r,\qquad c = j + k\cdot\Delta c.
  1. Verifique se 0 \le r < R e 0 \le c < C. Se alguma posição sair do intervalo, a palavra não cabe nessa direção a partir de (i,j).
  2. Se a posição estiver dentro do intervalo, compare o caractere da matriz em (r,c) com a k-ésima letra da palavra. Se for diferente, falha nessa direção.
  3. Se todos os k passarem (nenhuma falha e nenhuma saída de limites), então a palavra foi encontrada começando em (i,j) nessa direção. Registre (i,j).
Observações práticas:
  • Para evitar problemas com maiúsculas/minúsculas, é comum normalizar (por exemplo, transformar tudo em maiúsculas) antes de comparar. Isso facilita achar “Casa”, “casa” etc. O código que forneço faz essa normalização.
  • No enunciado o exemplo devolveu (1,3); o algoritmo que proponho, ao ler os dados e usar índices zero-based, obterá esse mesmo par para o exemplo.

Passo 5

Formato de entrada e detalhes de leitura (como o programa irá entender a entrada):
  • O programa espera primeiro dois inteiros: R e C (linhas e colunas).
  • Depois espera a matriz, R linhas cada uma com C caracteres. Para ser robusto ele aceitará tanto entradas onde os caracteres da linha vêm separados por espaços quanto linhas sem espaços (cadeia contínua de C caracteres).
  • Em seguida lê a palavra a buscar (uma única string).
  • Internamente, para ser ainda mais robusto, o programa pode ler todo o restante da entrada em tokens e decidir se os próximos R\cdot C tokens são células individuais ou se cada uma das próximas R tokens é uma linha com C caracteres. O código que vou fornecer faz essa estratégia para suportar formatos variados.

Passo 6

Exemplo prático (aplicando o método ao exemplo do enunciado):
Matriz exibida no enunciado (interpretação por linhas, R=3, C=6):
\begin{array}{cccccc} 1 & 2 & 3 & 4 & T & R \\\ A & S & A & C & R & T \\\\ 0 & X & G & T & B & K \end{array}
Palavra: “CASA” (comprimento L=4).
  • Primeiro procuramos células igual a ‘C’ (normalizando para maiúsculas). Achamos ‘C’ em (1,3) (linha 1, coluna 3 em zero-based).
  • Testando direção Oeste (0,-1): posições são (1,3)\to C, (1,2)\to A, (1,1)\to S, (1,0)\to A. Todas batem com “C”,“A”,“S”,“A”. Logo registramos (1,3). Esse é o resultado do exemplo.

Passo 7

Detalhes de saída e formatação final esperada:
  • Para cada ocorrência encontrada, imprimir uma linha com a tupla da posição inicial no formato (r,c) usando índices zero-based, exatamente como no exemplo: por exemplo (1,3).
  • O programa imprimirá uma linha por ocorrência, na ordem em que as células iniciais são varridas (linha por linha, da esquerda para a direita) e, para cada célula inicial, ao encontrar pelo menos uma direção que funcione, a posição é listada (se houver múltiplas direções que começam na mesma célula, não repetir a posição; basta reportá-la uma vez).
  • Se não houver ocorrências, o programa não imprimirá linhas (pode-se adaptar para imprimir alguma mensagem alternativa se desejado, mas deixei para não imprimir nada).

Passo 8

Resumo pedagógico final (para a prova):
  • Lembre-se: varrer todas as células e, para cada célula que bate com a primeira letra da palavra, testar as 8 direções com checagens de limites e comparação letra a letra.
  • Transforme caracteres para mesma caixa (upper/lower) para buscar sem diferenciar maiúsculas/minúsculas.
  • Tenha cuidado com índices (linha, coluna) e com o sentido positivo: linha cresce para baixo, coluna cresce para a direita.
  • Faça checagem de limites antes de acessar a matriz para evitar index-out-of-range.

Resposta

# Programa em Python que lê R, C, a matriz e a palavra e imprime as posições iniciais (zero-based)
# Aceita tanto entradas com células separadas por espaço quanto linhas contínuas.

import sys

def read_input_tokens():
    data = sys.stdin.read().strip().split()
    return data

def build_matrix_from_tokens(tokens, R, C):
    # tokens: lista de tokens restante (após R e C)
    # Tentativas:
    # 1) Se houver pelo menos R*C tokens, e cada token for 1 caractere, use-os diretamente.
    # 2) Se houver pelo menos R tokens e cada um tiver comprimento C, usar cada token como linha.
    # 3) Caso geral: concatenar tokens até ter R*C caracteres e dividir.
    if len(tokens) >= R * C + 1:
        # testar se os primeiros R*C tokens parecem ser células individuais (comprimento 1)
        first_rc = tokens[:R*C]
        if all(len(t) == 1 for t in first_rc):
            mat = []
            idx = 0
            for _ in range(R):
                row = first_rc[idx:idx+C]
                mat.append(row)
                idx += C
            word = tokens[R*C]
            return mat, word
    # caso 2: próximos R tokens são linhas contínuas de comprimento C
    if len(tokens) >= R + 1 and all(len(tokens[i]) == C for i in range(R)):
        mat = [list(tokens[i]) for i in range(R)]
        word = tokens[R]
        return mat, word
    # caso 3: concatenar todos tokens em uma única string (sem espaços) e pegar os primeiros R*C caracteres
    joined = "".join(tokens)
    if len(joined) < R * C + 1:
        # talvez não exista palavra depois; retornar vazio
        raise ValueError("Entrada insuficiente para matriz e palavra.")
    chars = list(joined)
    mat_chars = chars[:R*C]
    mat = []
    idx = 0
    for _ in range(R):
        row = mat_chars[idx:idx+C]
        mat.append(row)
        idx += C
    word = "".join(chars[R*C:]).split()[0] if len(chars) > R*C else ""
    # if word empty, try to fallback to tokens[-1]
    if not word and tokens:
        word = tokens[-1]
    return mat, word

def find_word_positions(mat, word):
    R = len(mat)
    C = len(mat[0]) if R>0 else 0
    L = len(word)
    if L == 0:
        return []
    # Normalizar maiúsculas para comparação (dígitos não mudam)
    MAT = [[cell.upper() for cell in row] for row in mat]
    W = word.upper()
    # direções: N, NE, L(E), SE, S, SO(SW), O(W), NO(NW)
    directions = [(-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1)]
    results = []
    for i in range(R):
        for j in range\text{(C)}:
            if MAT[i][j] != W[0]:
                continue
            matched = False
            for dr, dc in directions:
                ok = True
                for k in range(L):
                    r = i + k*dr
                    c = j + k*dc
                    if r < 0 or r >= R or c < 0 or c >= C:
                        ok = False
                        break
                    if MAT[r][c] != W[k]:
                        ok = False
                        break
                if ok:
                    matched = True
                    break
            if matched:
                results.append((i,j))
    return results

def main():
    tokens = read_input_tokens()
    if len(tokens) < 3:
        return  # entrada insuficiente
    try:
        R = int(tokens[0])
        C = int(tokens[1])
    except:
        # formato inesperado
        return
    remaining = tokens[2:]
    try:
        mat, word = build_matrix_from_tokens(remaining, R, C)
    except Exception as e:
        return
    positions = find_word_positions(mat, word)
    for (r,c) in positions:
        print(f"({r},{c})")

if __name__ == "__main__":
    main()

Exercícios relacionados