TP AEDS 3

Trabalho prático 2 – Número de caminhos
Departamento de Ciência da Computação – Universidade Federal de Minas Gerais
(UFMG)
Algoritmos e Estruturas de Dados III – 2014 / 2 [e-mail] 1. INTRODUÇÃO
O objetivo deste trabalho é descobrir o número de caminhos mais curtos partindo de um ponto A até um ponto B. Esses caminhos podem ser ilustrados como as ruas e avenidas de uma cidade, as ruas serão sempre horizontais e as avenidas verticais. Um detalhe importante é que algumas esquinas entre ruas e avenidas estarão fechadas. O ponto A sempre estará na primeira rua e avenida e poderá haver mais de um ponto B, sendo necessário calcular o número de caminhos mais curtos para cada ponto B.
Os dados que irão representar a cidade serão passados através de um arquivo de entrada. Assim sendo este arquivo conterá as dimensões da cidade, as esquinas bloqueadas, e os pontos B.

2. SOLUÇÃO PROPOSTA
A solução proposta para resolver este problema é construir uma estrutura de dados simples, matriz, as linhas da matriz irão representar as ruas e as colunas as avenidas.
A partir do arquivo de entrada alocar as dimensões da matriz com os inteiros X Y.
Definir as esquinas bloqueadas através da posição informada no arquivo de entrada Definir os pontos B através da posição informada no arquivo de entrada
Para calcular a quantidade de caminhos mais curtos usei permutação com repetição, dessa forma eu posso calcular a quantidade de caminhos mais curtos do ponto A até B.
Exemplo: Conforme figura abaixo um possível caminho do ponto A até B é
RRRRDDD, onde R é direita e D é baixo. A quantidade de caminhos menores é dada assim

= 35 caminhos mais curtos

Porém temos os casos em que as esquinas estão bloqueadas, conforme figura abaixo. Nesse caso calculamos o número de caminhos de A até B que passam pelo caminho bloqueado.
Exemplo: RRDD, onde R é direita e D é baixo.

= 6 caminhos que passam por esquina bloqueada

Para calcular a quantidade de