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.