MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 3818 6140

E-MAIL cef@ime.usp.br

MONITOR: MARCIO C. CABRAL

MAC 122 - Princípios de Desenvolvimento de Algoritmos

Segundo semestre de 2000

Exercício-Programa de Recuperação - Entrega: 8 de fevereiro de 2001

A casa maluca

Ao construir sua nova casa de campo, Mr. Black não deu muita atenção às idéias que o arquiteto tinha e implantava sem constrangimento. O que mais o incomodava (além da lavanderia no terceiro andar) era que as luzes dos quartos não eram acesas e apagadas por interruptores que se localizavam no mesmo quarto, mas em quartos diferentes. O arquiteto achava a idéia o máximo, e Mr. Black, quando foi passar as primeiras férias lá, para lá de maluca.

O grande problema é que o Sr. Black tinha medo de andar no escuro, e, ao mesmo tempo era um tremendo sovina. Assim, ele queria se deslocar à noite pela casa sem andar no escuro, mas, ao chegar no quarto onde desejava ir, queria que todas as outras lâmpadas da casa estivessem apagadas.

Então, o Sr. Black resolveu contratar os serviços dos internacionalmente famosos alunos do BCC para escrever um programa que, dada uma casa maluca como a dele, um quarto de saída e um quarto de chegada, mostrasse uma seqüência mínima de operações do tipo ``acenda a luz do quarto $i$'', ``vá para o quarto $j$'' que o leva do quarto de saída ao quarto de chegada passando apenas por quartos acesos e, ao chegar, todas as outras lâmpadas da casa estejam apagadas. Seu programa deverá indicar ao Mr. Black as operações, ou, caso não seja possível chegar ao quarto que ele deseja, informar isso.

Seu programa deve permitir a entrada de uma planta de casa, dada pelo número de cômodos da mesma, e, para cada cômodo, a lista das portas deste cômodo (indicando a que cômodo a porta leva) e a lista de interruptores do cômodo (indicando de que quartos a luz é acesa/apagada neste interruptor). Outra opção de seu programa deverá ser gerar aleatoriamente casas malucas.

A entrega deste exercício-programa deverá ser marcada com o professor, pois a correção será feita durante a entrega.

Dicas

• Este exercício não é muito fácil. Acredito que você levará pelo menos uma semana para resolvê-lo (com dedicação exclusiva)!!

• Note que o problema por trás do pedido do Mr. Black parece muito com o problema de levar o ratinho até o queijo em um labirinto...

• Utilize necessariamente listas ligadas para armazenar os dados que surgem no problema (ex. a lista de portas de um cômodo).

• Se você fizer uma animação para mostrar ao Mr. Black o melhor jeito de chegar ao quarto desejado seguindo as regras, pode contar com um bônus na sua nota.

• Boas férias!!