Solução Informática – Nível Iniciante – Semana 39

Solução escrita por Arthur Lobo

Conhecimento prévio necessário:

• Busca em grafos

Primeiro, vamos reduzir o problema inicial para um grafo: cada posição $(i,j)$ representará um vértice e vamos criar arestas entre vértices que sào vizinhos e ambos não estão bloqueados, ou seja, se um está pintado o outro também será.

Formalmente, vamos adicionar uma aresta de $(i,j)$ para $(i',j')$ se $(i',j')$ for um dos $8$ vizinhos de $(i,j)$, ou seja, for um dos $(i-1,j-1),(i-1,j),(i-1,j+1),(i,j-1),(i,j+1),(i+1,j-1),(i+1,j),(i+1,j+1)$ e ambos não estão bloqueados.

Se o primeiro quadradinho a ser pintado for $(X,Y)$, então todos os quadradinhos que $(X,Y)$ consegue chegar também serão pintados, ou seja, todos que estão na mesma componente conexa, que ele.

Portanto, basta montar esse grafo e depois rodar uma dfs partindo de $(X,Y)$ e ver o tamanho da sua componente conexa, que pode ser feito em $O(N*M)$.

Clique aqui para conferir o código