[Caça ao tesouro] Neste problema você deve escrever uma função que receba uma matriz de números naturais com exatamente dois dígitos. Cada entrada da matriz tem uma dica para a próxima posição a ser visitada. O dígito das dezenas indica a linha e o dígito das unidades indica a coluna da próxima posição. Começando na posição [1,1], siga as dicas até encontrar a posição onde o número leva à própria posição. Essa posição é onde o tesouro está escondido. Seu programa deve imprimir as posições visitadas durante a busca e, ao final, indicar onde o tesouro foi encontrado. Por exemplo, considere a seguinte matriz:
34
21
32
41
25
14
52
43
14
31
54
45
52
42
23
33
15
51
31
35
21
52
33
13
23
O programa deve imprimir as seguintes posições visitadas:
Pede-se escrever uma função que, dada uma matriz cujas entradas são números naturais de exatamente dois dígitos, siga “dicas” contidas nas células até encontrar a posição que aponta para si mesma (o tesouro). A saída deve mostrar as posições visitadas durante a busca e, ao final, indicar onde o tesouro foi encontrado.
Regras da dica: se uma célula contém o número de dois dígitos ab (onde a é o dígito das dezenas e b o das unidades), então ela indica a próxima posição [a,b] (linha a, coluna b). As linhas e colunas são indexadas começando em 1.
Começa-se em [1,1] e segue-se as dicas até encontrar uma posição [r,c] tal que o número na posição [r,c] é exatamente 10r+c (ou seja, aponta para si mesma).
O enunciado fornece uma matriz de exemplo (peguei os valores do enunciado):
Perguntas explícitas a responder: mostrar a sequência de posições visitadas a partir de [1,1] até o local do tesouro; indicar a posição do tesouro.
Passo 2
Ideia do método (sem resolver ainda) e ferramentas matemáticas básicas necessárias.
Estratégia escolhida: simular o passeio seguindo as dicas, guardando a sequência de posições visitadas até achar a célula que aponta para si mesma. Esta estratégia é direta, eficiente e apropriada para o problema.
Como extrair a próxima posição de um número de dois dígitos n:
o dígito das dezenas é \left\lfloor \dfrac{n}{10} \right\rfloor;
o dígito das unidades é n \bmod 10.
Exemplo: para n=34, \left\lfloor \dfrac{34}{10} \right\rfloor=3 e 34\bmod 10=4, logo aponta para [3,4].
Condição de parada (tesouro): estando em [r,c] e com n o valor na célula [r,c], o tesouro está aqui se e somente se
n = 10r + c.
Prevenção contra loops infinitos (precaução prática): manter um conjunto/lista das posições já visitadas; se for encontrado novamente um próximo passo que já foi visitado e esse passo não é um ponto que aponta para si mesmo, isso indica um ciclo sem tesouro (mas o enunciado assume caso bem-formulado onde o tesouro é alcançável). Ainda assim, implementar a verificação evita laços infinitos na execução.
Passo 3
Pseudocódigo claro e comentado (passo a passo que você pode implementar na prova).
Representação: a matriz será chamada de M. Use indexação 1-based nas explicações. Comece em r=1, c=1.
Pseudocódigo (descrito em passos verbais fáceis de converter para qualquer linguagem):
Inicialize \text{seq} \leftarrow lista vazia para armazenar as posições visitadas.
Defina r \leftarrow 1, c \leftarrow 1.
Enquanto verdadeiro:
Anexe [r,c] ao final de \text{seq}.
Leia n \leftarrow M[r,c].
Calcule r_{\text{prox}} \leftarrow \left\lfloor \dfrac{n}{10} \right\rfloor e c_{\text{prox}} \leftarrow n \bmod 10.
Se n = 10r + c então pare: encontrou o tesouro em [r,c].
Senão, se [r_{\text{prox}},c_{\text{prox}}] já está em \text{seq} então pare para evitar loop (opcional: reportar erro). Caso contrário, atualize r \leftarrow r_{\text{prox}}, c \leftarrow c_{\text{prox}} e repita.
Observações práticas:
Ao implementar em linguagens com indexação 0-based (ex.: C, Java, Python), faça a conversão apropriada ao acessar a matriz: M[r,c] na nossa notação 1-based corresponde a M[r-1][c-1].
A extração de dígitos é simples com operadores inteiros: em pseudocódigo, r_{\text{prox}} = n \div 10 e c_{\text{prox}} = n \bmod 10.
Passo 4
Aplicando o método passo a passo no exemplo fornecido — vou seguir a sequência desde [1,1] e mostrar cada cálculo explicitamente.
Estado inicial: [r,c]=[1,1]. Anoto [1,1] na sequência.
Verifico se 52 = 10\cdot 5 + 2 = 52. Sim! Condição de tesouro satisfeita → pare aqui.
Sequência completa de posições visitadas (na ordem): [1,1]\rightarrow[3,4]\rightarrow[4,2]\rightarrow[1,5]\rightarrow[2,5]\rightarrow[3,1]\rightarrow[5,4]\rightarrow[1,3]\rightarrow[3,2]\rightarrow[4,5]\rightarrow[3,5]\rightarrow[2,3]\rightarrow[4,3]\rightarrow[5,1]\rightarrow[2,1]\rightarrow[1,4]\rightarrow[4,1]\rightarrow[3,3]\rightarrow[5,2].
O tesouro ficou em [5,2] porque nessa posição o número é 52, que aponta exatamente para [5,2].
Passo 5
Como imprimir/formatar a resposta na prática e dicas finais rápidas.
Formato sugerido (exatamente o que o enunciado pediu): imprimir a sequência de posições visitadas com setas (\rightarrow) e, em seguida, indicar a posição do tesouro.
Em código: construa a lista \text{seq} durante a simulação e depois mostre algo como
primeira linha: [1,1] \rightarrow [3,4] \rightarrow \cdots \rightarrow [5,2]
segunda linha: [5,2] (ou uma legenda curta, por exemplo, “Tesouro em [5,2]”).
Dica de prova: memorize a operação para extrair dezenas e unidades (divisão inteira por 10 e resto por 10). Sempre registre as posições visitadas para evitar laços infinitos durante código/manual.