MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 3818 6140

E-MAIL cef@ime.usp.br

MONITOR: MARCIO C. CABRAL

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 '', ``v� para o quarto '' 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!!

• About this document ...