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:
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):
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.
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).
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.
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
defread_input_tokens():
data = sys.stdin.read().strip().split()
return data
defbuild_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.iflen(tokens) >= R * C + 1:
# testar se os primeiros R*C tokens parecem ser células individuais (comprimento 1)
first_rc = tokens[:R*C]
ifall(len(t) == 1for t in first_rc):
mat = []
idx = 0for _ inrange(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 Ciflen(tokens) >= R + 1andall(len(tokens[i]) == C for i inrange(R)):
mat = [list(tokens[i]) for i inrange(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)
iflen(joined) < R * C + 1:
# talvez não exista palavra depois; retornar vazioraise ValueError("Entrada insuficiente para matriz e palavra.")
chars = list(joined)
mat_chars = chars[:R*C]
mat = []
idx = 0for _ inrange(R):
row = mat_chars[idx:idx+C]
mat.append(row)
idx += C
word = "".join(chars[R*C:]).split()[0] iflen(chars) > R*C else""# if word empty, try to fallback to tokens[-1]ifnot word and tokens:
word = tokens[-1]
return mat, word
deffind_word_positions(mat, word):
R = len(mat)
C = len(mat[0]) if R>0else0
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 inrange(R):
for j inrange\text{(C)}:
if MAT[i][j] != W[0]:
continue
matched = Falsefor dr, dc in directions:
ok = Truefor k inrange(L):
r = i + k*dr
c = j + k*dc
if r < 0or r >= R or c < 0or c >= C:
ok = Falsebreakif MAT[r][c] != W[k]:
ok = Falsebreakif ok:
matched = Truebreakif matched:
results.append((i,j))
return results
defmain():
tokens = read_input_tokens()
iflen(tokens) < 3:
return# entrada insuficientetry:
R = int(tokens[0])
C = int(tokens[1])
except:
# formato inesperadoreturn
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()