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:

1. todos os pixels de uma região têm a mesma cor;

2. 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.

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:

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.

← Anterior Voltar Próximo →