Prazo de entrega recomendado:
Você deve encontrar um caminho em um mapa com poucas regiões.
Maria acaba de ser aprovada na universidade e ainda não conhece o campus. Prevenida, antes de viajar ela quer se certificar de que sabe sair da sala de aula e chegar no restaurante. Para isso, procurou um mapa da universidade. Distraída (e cheia de coisas novas na cabeça), quanto menos coisa para lembrar melhor!
Uma imagem pode ser representada por uma matriz de inteiros, onde cada célula é chamada de pixel e cujo valor é um inteiro. Cada número inteiro representa uma cor distinta.
Um mapa nada mais é do que uma imagem de uma certa área, que representa informações geográficas. Mais precisamente, um mapa de regiões é uma imagem tal que:
-
todos os pixels de uma região têm a mesma cor;
-
regiões adjacentes têm cores distintas.
Dizemos que duas regiões são adjacentes se dois de seus pixels o forem. Dois pixels são adjacentes se um está imediatamente em cima ou imediatamente do lado do outro. A figura abaixo ilustra um pixel p e seus pixels adjacentes, a.
O seu objetivo é ajudar Maria a encontrar um caminho entre duas
regiões que passa pelo menor número de regiões (e diminuir a chance de
que ela se perca!). Escreva um programa caminhos
que receba um mapa
em PPM e conte o menor número regiões entre duas regiões marcadas com
a cor branca.
Entrada
Um mapa de regiões no formato PPM com exatamente duas regiões brancas.
![](mapa.png)
Saída
O menor número de regiões por que se deve passar para ir de uma região à outra.
Maria deve memorizar 5 regioes.
Nesse exemplo, Maria deveria passar pelo Ciclo Básico (azul), bloco do RU (verde), Av. Érico Veríssimo (cinza), Av. Alan Turing (cinza claro) e bloco do RS (verde). O caminho está destacado abaixo:
![](caminho.png)
Dicas
-
Um esboço de código para leitura e escrita de imagens PPM está disponível no arquivo
exemplo.c
. Vocês podem usar esse código. -
Você pode supor que não existem regiões pretas nos casos de teste.
Critérios
É obrigatório resolver o problema utilizando os conceitos de grafos. Faça um pequeno comentário na função que deixa explícito quais são os elementos do grafo considerado. Você pode utilizar a representação do grafo que for mais conveniente para seu algoritmo, que pode representar os elementos do grafo direta ou implicitamente.
Correção
Esta tarefa será corrigida automaticamente sempre que você realizar um
git push
. Depois de terminada a tarefa, deve-se utilizar o botão na
interface de notas para solicitar a correção de um monitor.