Solução Informática - Nível Iniciante - Semana 31

Escrito por Estela Baron

Conhecimento prévio necessário:

Nesse problema, se representarmos cada espaço de piso como um vértice de um grafo, podemos dizer que há uma aresta bidirecional de $u$ para $v$ , desde que, tanto $u$ quanto $v$ sejam pisos e sejam adjacentes entre si (ou um está em cima, ou embaixo, ou à direita, ou à esquerda do outro).

Portanto, para achar a resposta, basta achar quantas componentes conexas existem em nosso grafo. Para isso, vamos montar uma matriz em que cada posição guarda ou o valor 1 ou o valor 0, representando a presença de uma parede ou de um piso, respectivamente.

Em seguida, executamos uma $dfs(int \;x,int \; y)$ para cada posição de piso que não foi visitada ainda. Toda vez que fazemos isso, estamos iniciando a busca em uma nova componente, pois significa que a posição atual não fazia parte de nenhuma das anteriores. Logo, a nossa resposta aumenta em um.

A função $dfs(int \;x, int \;y)$ vai funcionar da seguinte forma: primeiro, vamos marcar em nossa matriz de $vis[\; ][ \;]$ que o vértice $(x, y)$ foi visitado. Em seguida, iremos ver se os pares de ordenadas adjacentes ao da nossa posição, que são os pares $(x+1, y), (x-1, y), (x, y+1), (x, y-1)$ , são válidos. Um vértice é válido se, e somente se, $0\leq x < n$ , $0\leq y<m$ , se ele representar um piso e se ele não tiver sido visitado. Caso o novo par for uma posição válida, chamamos a função $dfs$ para ele.

Ao final, teremos contado a quantidade de componentes conexas, que representa quantos quartos há. Portanto, só precisamos imprimir a solução.

Observação: na hora de visitar as posições adjacentes, tente achar uma forma de não ter que fazer "na mão" todos os casos, ou seja, fazer $if(0\leq x \; and \; x< n \;and \; 0\leq y \; and \; y<m\; and \;matriz[\; x][\;y+1] == 0)$ . Um exemplo de como fazer isso está no código.

Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.