fab

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Considere uma matriz N x N preenchida com '0's (poros fechados) e '1's (poros abertos) aleatórios usada para modelar um material poroso. Queremos descobrir se água nos poros abertos ('1's) da primeira linha pode escorrer até a última linha passando apenas por poros abertos ('1's) adjacentes verticais ou horizontais.

1111111111111          (saída)
0001001100000
0010000110000
0100000010000          (a água escorre pelo caminho a direita
1000000011100           mas não pelo caminho a esquerda)
0100000000100
0010000000110
1111111111111          (chegada)

Considere as seguintes afirmações: 

I. Esse problema pode ser resolvido usando a estrutura union-find balanceada e com compressão de caminho em O(n² lg* n²).

II. A abertura de um poro qualquer (trocar '0' por '1') pode implicar em até quatro chamadas do de union.

III. Mesmo usando compressão de caminho, uma chamada de find pode levar mais que n/2 passos.

A) Apenas II é verdadeira.

B) I e II são verdadeiras.

C) Todas são verdadeiras.

D) I e III são verdadeiras.

E) NDA

Ideia original de: Fabrício Matheus Gonçalves