Solução escrita por Arthur Lobo
Conhecimento prévio necessário:
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