Chuva

Está chovendo tanto na Obilândia que começaram a aparecer goteiras dentro da casa do prefeito. Uma dessas goteiras está fazendo escorrer água verticalmente, a partir de um ponto no teto, numa parede onde há várias prateleiras horizontais. Quando a água bate em uma prateleira, ela começa a escorrer horizontalmente para os dois lados, direita e esquerda, até as extremidades da prateleira, quando volta a escorrer verticalmente. Vamos representar a parede por uma matriz de N linhas e M colunas de caracteres, como mostrado ao lado. As prateleiras serão representadas por “#” e a parede por “.”. Só existem prateleiras nas linhas pares e elas nunca encostam na borda da parede. Há apenas um ponto de vazamento representado pelo caractere “o” na primeira linha.

Para deixar mais rigorosa a forma como a água vai escorrer, seja c(i, j) o caractere na linha i coluna j. Se c(i, j)= “.”, então ele deve virar “o” sempre que:

• c(i − 1, j)= “o”; ou

• c(i, j − 1)= “o” e c(i + 1, j − 1)= “#”; ou

• c(i, j + 1)= “o” e c(i + 1, j + 1)= “#”. 

Neste problema, dada a matriz representando a parede no início do vazamento, seu programa deve imprimir na saída uma matriz representando a parede usando o caractere “o” exatamente nas posições que serão molhadas pelo vazamento, como ilustrado acima.