next up previous
Next: Exerc�cio-programa

Departamento de Ci�ncia da Computa��o - IME-USP

MAC 115 - Introdu��o � Computa��o para Ci�ncias Exatas e Tecnologia

INSTITUTO DE F�SICA - SEGUNDO SEMESTRE DE 2001 - BACHARELADO NOTURNO

Terceiro Exerc�cio-Programa (EP3)Prazo de entrega: 29 de novembro de 2001

Alaga��es na USSP

Devido a um forte temporal que caiu em S�o Paulo, v�rias regi�es da cidade universit�ria da USSP (Universidade de S�bios Samaritanos Pragm�ticos) ficaram alagadas. Representamos o campus da USSP por um reticulado, como o da figura abaixo, onde $0$ representa uma posi��o seca e $-1$ representa uma posi��o alagada.

$-1$ 0 0 0 0 $-1$ $-1$ 0 $-1$ $-1$
$-1$ $-1$ $-1$ 0 0 0 $-1$ 0 $-1$ 0
0 $-1$ 0 0 $-1$ 0 0 0 0 0
0 0 0 $-1$ $-1$ $-1$ $-1$ $-1$ 0 0
0 0 0 0 $-1$ $-1$ 0 0 $-1$ $-1$
0 0 $-1$ 0 0 0 0 $-1$ $-1$ $-1$
0 0 $-1$ $-1$ $-1$ 0 0 0 $-1$ $-1$
$-1$ 0 $-1$ $-1$ $-1$ $-1$ 0 0 0 $-1$
$-1$ 0 0 0 0 0 $-1$ $-1$ 0 0
$-1$ 0 0 0 0 0 $-1$ 0 0 0

Dizemos que duas posi��es deste reticulado s�o adjacentes se possuem uma aresta em comum. Uma regi�o R � definida como um conjunto de posi��es tal que � poss�vel a partir de uma posi��o de R, atingir qualquer outra posi��o de R atrav�s de posi��es adjacentes. Se todas as posi��es de uma regi�o cont�m $-1$ ent�o a regi�o � dita alagada. Uma regi�o alagada maximal � uma regi�o alagada que n�o est� contida em nenhuma regi�o alagada a n�o ser ela mesma.


next up previous
Next: Exerc�cio-programa
Yoshiko Wakabayashi
2001-11-08