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)
Para simular um material desconhecido, podemos abrir poros, isso é trocar '0' por '1', até que ele filtre, mas uma vez aberto um poro nunca muda para fechado durante uma simulação.
Sabendo que esse problema pode ser modelado usando a estrutura union-find balanceada e com compressão de caminho, considere as seguintes afirmações:
I. Podemos responder se uma matriz fixa de entrada permite a passagem da água em O(n² lg* n²).
II. Durante uma simulação, a abertura de um poro qualquer implica em até quatro chamadas de union.
III. Durante uma simulação, uma chamada de find pode levar mais que lg* n² passos.
A) Apenas I é verdadeira.
B) Apenas II é verdadeira.
C) Somente II e III são verdadeiras.
D) Todas são verdadeiras.
E) NDA
Ideia original de: Fabrício Matheus Gonçalves
Nenhum comentário:
Postar um comentário