Introdução
Planeias construir uma casa na árvore num bosque perto da tua casa, para poderes ver o nascer e o pôr do sol.
Obtiveste dados de uma empresa de topografia local que mostram a altura de cada árvore em cada secção retangular do mapa.
Precisas de analisar cada grelha do mapa para encontrares boas árvores para a tua casa na árvore.
Uma boa árvore é, ao mesmo tempo:
- mais alta do que qualquer árvore a leste e a oeste, para teres a melhor vista possível do nascer e do pôr do sol.
- mais baixa do que qualquer árvore a norte e a sul, para minimizares a quantidade de vezes que tens de trepar às árvores.
Instruções
A tua tarefa é encontrar as árvores potenciais onde podes construir a tua casa na árvore.
A empresa de dados fornece os dados em grelhas que mostram as alturas das árvores.
As linhas da grelha representam a direção este-oeste e as colunas representam a direção norte-sul.
Uma árvore aceitável é a maior da sua linha e, ao mesmo tempo, a menor da sua coluna.
Uma grelha pode não ter nenhuma árvore boa.
Ou pode ter uma, ou até várias.
Eis uma grelha que tem exatamente uma árvore candidata.
↓
1 2 3 4
|-----------
1 | 9 8 7 8
→ 2 |[5] 3 2 4
3 | 6 6 7 1
- A linha 2 tem os valores 5, 3, 2 e 4. O maior valor é 5.
- A coluna 1 tem os valores 9, 5 e 6. O menor valor é 5.
Portanto, o ponto em [2, 1] (linha: 2, coluna: 1) é um excelente sítio para uma casa na árvore.
Os índices em Rust começam em 0
Por convenção, as sequências ordenadas de valores em Rust têm o seu conteúdo numerado ("indexado") a partir de 0. Isto aplica-se independentemente do que o resto da descrição do exercício neste README diga, como referências a índices que começam em 1, pelo que terás de subtrair 1 para traduzir esses números de índice para os números de índice de Rust.
Nota sobre a eficiência
Este exercício usa um vetor de vetores para guardar o conteúdo de matrizes. Embora este exercício tenha sido concebido para ajudar os estudantes a compreender conceitos básicos sobre vetores, como a indexação, e que os tipos de dados aninhados são válidos, o vetor de vetores é uma escolha pouco ideal para álgebra de matrizes de alto desempenho e para qualquer processamento eficiente semelhante de maiores quantidades de dados.
A explicação detalhada desta ineficiência está além do âmbito deste exercício e deste percurso de aprendizagem em geral. Este aspeto é conhecido como localidade de cache e podes encontrar uma boa introdução ao mesmo clicando nessa ligação, se quiseres saber mais sobre detalhes de uma arquitetura de computador moderna.
