MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 3091 6140

E-MAIL cef@ime.usp.br

MONITOR Paulo E. Silveira

E-MAIL peas@ime.usp.br

MAC 122 - Princípios de Desenvolvimento de Algoritmos
http://panda.ime.usp.br

Exercício-Programa 4 - Entrega: 27 de novembro

Guerra em Pandópolis!!!!!

Pandópolis era um lugar tranqüilo. Todos viviam em paz até que surgiram as desavenças entre os dois países vizinhos de Pandópolis: Fundistão e Restônia. Os conflitos foram ficando cada vez maiores até que o Presidente Ervilhas, líder de Pandópolis, até então neutro nas disputas, resolveu se aliar à Restônia. Os guerreiros de Fundistão invadiram Pandópolis, e levaram à situação que agora vemos.

A fim de ajudar seus aliados, o Gal. Low$\pi$s de Restônia mandou atiradores de elite, liderados pelo Cel. D.D.P.X.L. para defender os principais prédios da capital do país, e impedir um ataque de Fundistão ao palácio do Pres. Ervilhas. O posicionamento destes atiradores é secreto, e vem dizimando os soldados de Fundistão que se aventuram na cidade. Preocupado com a situação, o Cel. Monstro (chamado de ``Cel. Nanico'' pelos habitantes de Fundistão :-)) mandou especialistas da SIFU (Serviço de Inteligência de Fundistão) que puderam ter acesso a algumas ruas livres de atiradores, assim como informações parciais de onde estavam atiradores em determinados pontos de referência da cidade.

Sua tarefa é, de posse destas informações, determinar se é possível a um soldado de Fundistão (de nome MinusFive e que tem pontaria perfeita) com $k$ balas chegar à localização em que se encontra o presidente de Pandópolis (que a SIFU também pôde descobrir). MinusFive deve andar apenas por ruas seguras, e, quando chegar a uma posição em que sabe existir um atirador de Restônia deve gastar uma de suas balas antes de seguir viagem. Note que se a SIFU determinou que uma rua é segura no trecho que vai de ``A'' a ``B'', também é segura no trecho que vai de ``B'' a ``A''.

A entrada para este programa é dada pelas informações que a SIFU pôde obter sobre os atiradores. Assim, a entrada é dada por uma lista de $m$ trechos seguros de ruas, dados através de pares de pontos de referência (strings separadas por brancos). Além disso, são dados $n$ pontos de referência em que temos certeza de que há um atirador de tocaia. Finalmente é dado o número $k$ de balas de que o soldado dispõe, uma entrada segura da cidade e a localização do presidente, segundo a SIFU.

Exemplo: Considere os dados abaixo, em que a SIFU descobriu 7 trechos seguros de ruas, 3 localizações de atiradores de Restônia e o soldado MinusFive tem 1 bala. Desejamos verificar se é possível a MinusFive ir do ``Portão-de-Login'' (entrada da cidade) até a ``Casa-da-Marquesa'' (localização do Pres. Ervilhas, segundo a SIFU).

7
Portão-de-Login Praça-Central
Praça-Central Obelisco
Praça-Central Estátua-do-Presidente-Ervilhas
Praça-Central Cemitério
Estátua-do-Presidente-Ervilhas Cemitério
Casa-da-Marquesa Estátua-do-Presidente-Ervilhas
Cemitério Casa-da-Marquesa
3 
Praça-Central
Obelisco
Cemitério
1
Portão-de-Login
Casa-da-Marquesa

Para o exemplo acima a resposta deve ser ``SIM'', pois o caminho que passa por: Portão-de-Login, Praça-Central, Estátua-do-Presidente-Ervilhas, Casa-da-Marquesa gasta apenas uma bala.