Lhama

1. Revisão de Conceitos

Para resolver esse problema, você precisará dominar dois conceitos principais em Python: Matrizes (Listas de Listas) irregulares e o cálculo de Distâncias.

Matrizes com Linhas de Tamanhos Diferentes

Em muitos problemas, trabalhamos com matrizes perfeitas (ex: $5 \times 5$). No entanto, se você observar os casos de teste, o mapa do terreno possui linhas com quantidades de colunas diferentes.

Isso significa que, para uma linha i, a quantidade de colunas não é fixa. Você pode usar a função len(terreno[i]) para saber até qual coluna j você pode iterar naquela linha específica.

Acessa uma posição que não existe em uma linha (ex: terreno[i][j] onde j >= len(terreno[i]) ou j < 0) resultará em um IndexError. Fique atento a isso, especialmente quando estiver verificando os vizinhos de uma lhama.

Adjacência (Vizinhança de 8 posições)

Para verificar se uma lhama está sozinha, você precisa olhar ao redor dela (horizontal, vertical e diagonais). Se a lhama está na posição (i, j), seus vizinhos estão nas posições:

  • Linha de cima: (i-1, j-1), (i-1, j), (i-1, j+1)
  • Mesma linha: (i, j-1), (i, j+1)
  • Linha de baixo: (i+1, j-1), (i+1, j), (i+1, j+1)

Distância de Manhattan

A distância entre dois pontos $(x_1, y_1)$ e $(x_2, y_2)$ em um plano de grade (onde você só pode andar na vertical e horizontal) é dada pela fórmula:

$$d = |x_1 - x_2| + |y_1 - y_2|$$

Em Python, a operação de módulo (valor absoluto) é feita utilizando a função nativa abs(). Por exemplo, abs(-5) resulta em 5.

Em vários momentos do código você precisará saber a distância entre dois “pontos”. Será que uma função que dadas as 4 coordenadas retorna a distância de Manhattan entre elas pode ser útil?

def distancia_manhattan(x1: int, y1: int, x2: int, y2: int) -> int:
    ...

2. Dicas de Estruturação (Por onde começar?)

Um erro comum ao lidar com problemas complexos é tentar fazer tudo em uma única passagem (um grande for dentro de outro for). Quebrar o problema em partes menores facilita muito a vida:

  1. Antes de tentar descobrir se as lhamas estão em perigo ou sozinhas, será que temos como achar onde lhamas estão e onde estão as fontes de água/comida?
  2. Com as lhamas mapeadas, podemos conferir sua vizinhança para descobrir se ela está vazia?
  3. Para cada lhama, você precisa calcular a distância dela para todas as fontes de água/comida. Ela só precisa estar próxima de uma fonte para estar tranquila!
    • DICA! Existem 2 testes abertos que não possuem lhamas em perigo. Garanta que seu código está passando nesses testes antes de começar a codar essa parte.

3. Problemas e Erros Comuns

Fique atento a estes pontos durante a implementação e os testes. Eles costumam ser a principal causa de erros:

O temido IndexError (Acesso fora dos limites da lista):

Ao verificar os vizinhos de uma lhama, você pode acidentalmente tentar acessar uma linha que não existe (ex: linha -1 ou linha L). Pior ainda: como as linhas têm tamanhos diferentes, a coluna j+1 pode existir na linha i, mas não existir na linha i-1. Sempre verifique se o índice da linha é válido e, em seguida, se o índice da coluna é válido para aquela linha específica, antes de acessar o valor no terreno.

Lhamas em perigo (Lógica do “Menor que”):

Uma lhama só está em perigo se ela estiver longe de todas as fontes. Se houver 3 fontes no mapa, e as distâncias forem 10, 8 e 1 (sendo $D = 2$), a lhama não está em perigo, pois existe pelo menos uma fonte a uma distância segura.

Formatação da Saída:

Preste muita atenção aos requisitos do enunciado.

  • As coordenadas devem ser impressas separadas por vírgula e espaço: (0, 1), (1, 2). Se você guardar as coordenadas em uma tupla, é só imprimir a tupla.
  • Se a quantidade (X ou Y) for zero, a frase muda.

Variáveis “vazando” nos loops:

Ao usar variáveis para contar coisas (como a menor distância encontrada até o momento, ou uma flag booleana sozinha = True), lembre-se de resetar ou redefinir essas variáveis toda vez que começar a analisar uma nova lhama.

Bom trabalho no desenvolvimento do código! Testem cada comando isoladamente antes de juntar tudo no programa final e podem me mandar as dúvidas por email!