DFS em grid

Tutorial por Murilo Maeda

Conhecimento prévio necessário

Introdução à DFS em grid

Para introduzir esse tópico, vamos começar com um problema base:

Um tabuleiro NxM possui algumas casas pintadas. Duas casas pintadas esão na mesma mancha se é possível ir de uma casa até outra passando apenas por outras casas pintadas ortogonalmente adjacentes (compartilham um lado). Conte o número de manchas no tabuleiro.

No tabuleiro da imagem, casas em cinza estão pintadas e as casas pintadas com o mesmo número estão na mesma mancha.

Problema original

Solução

Perceba que precisamos saber determinar se um grupo de casas estão conectadas ou não. Isto é, contar o número de componentes, assim como podemos fazer em problemas de grafo, usando DFS! Se você não sabe contar o número de componentes em um grafo usando DFS, cheque a aula desse assunto no NOIC antes. Mas, como podemos transformar o tabuleiro em um grafo?

Veja que, como queremos checar as casas to tabuleiro que estão na mesma mancha, faz sentido considerar cada casa pintada como um vértice. E como consideramos vértices que compartilham um mesmo lado como vizinhos, as arestas são entre casas que possuem um lado em comum e que estão ambas pintadas.

Por fim, basta percorrer o grafo que foi criado e executar o algoritmo de contar componentes.

Construindo o Grafo

Perceba que só com o tabuleiro já temos todas as informações do grafo, isto é, quem são os vértices e quem são seus vizinhos. Então, diferente de uma DFS normal, que passa pela lista de adjacência de cada vértice, na DFS em grid podemos percorrer os vizinhos passando pelas casas que possuem um lado em comum com a atual, como é representado na figura.

Veja que, a partir da casa atual, só precisamos checar as 4 casas verdes. As 4 casas vermelhas não precisam ser checadas a partir da casa atual, já que no nosso grafo as arestas são só entre casas com um lado em comum.

Segue o código para maior esclarecimento:

Truque DiDj (lê-se Dê I Dê Jota)

Esse truque serve para passar mais facilmente pelas casas vizinhas da casa atual em uma DFS em grid. Esse truque funciona da seguinte forma: criamos dois vetores : dI e  dJ. Os vetores são organizados de modo que, para qualquer número k tal que 0 \leq k \leq tamanho dos vetores, o par formado por di[k] e dj[k] forma uma das possíveis variações para chegar em um vizinho a partir da posição atual. dI guarda as variações na coordenada i e dJ guarda as variações na coordenada j.

Por exemplo, se dI = {1,-1,0,0} e dJ = {0,0,1,-1}, as casas que serão consideradas como vizinhas serão:

É importante perceber que a ordem dos elementos em cada vetor é importante, já que cada k representa um par de números.

Além disso, é possível generalizar para que cada k represente qualquer mudança para checar os vizinhos, não só as representadas acima.

Por exemplo, se dI = {1,-1,1,-1,0,0} e dJ = {0,0,1,-1,1,-1}, todas as 8 casas ao redor da atual serão consideradas como vizinhos. Tente ver sozinho o porquê disso.

O código fica da seguinte forma:


int dI[4] = {1,-1,0,0};
int dj[4] = {0,0,1,-1};
//limite do i e do j, respectivamente
int N,M;
dfs(int i, int j)
{
for(int k = 0; k < 4; k++)
{
int vizI = i + dI[k];
int vizJ = j + dJ[k];
//lembre-se sempre de checar se as coordenadas obtidas a partir do truque são válidas
if(vizI > N || vizI <= 0 || vizJ > M || vizJ <= 0) continue;
//dependendo do problema (como é o caso do problema base), pode ser que seja necessário checar alguma condição sobre a casa em si
//Para não acessar posição inválida, faça isso depois de verificar que as coordenadas novas estão dentro da Matriz
}
}

view raw

TruqueDiDj.cpp

hosted with ❤ by GitHub

Para problemas gerais de DFS em grid

  • Adapte a checagem de vizinhos de acordo com as condições do problema
  • Adapte o truque DiDj de acordo com o problema

Mais Problemas