Solução Colorindo

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

Este é um problema simples de Flood Fill, feito com uma única DFS. Se você não conhece algoritmos de Flood Fill, clique aqui para ver a aula do Curso Noic sobre o assunto. Usaremos uma matriz booleana tab para salvarmos o tabuleiro. Os quadrados que guardarem o valor false podem ser pintados, e os que guardarem true, não (são pretos ou já foram pintados). Usaremos, também, o inteiro qtd para guardarmos quantos já foram. Desse modo, quando chamarmos a DFS em um quadrado, devemos verificar primeiro se podemos pintá-lo (se ele está dentro do tabuleiro e se sua posição em tab guarda false), retornando caso isso ocorra. Feito isso, iremos pintá-lo (marcamos sua posição com true na matriz tab e aumentamos o valor de qtd em uma unidade) e percorrer todos os seus vizinhos, chamando a DFS para cada um deles. Na main, basta lermos os valores de n, m, x, y e k, marcarmos com true em tab todos os quadrados pretos, chamarmos a DFS para o quadrado inicial (x, y) e imprimirmos o valor de qtd. Segue o código para melhor entendimento:

Nosso leitor Roger Benet também apresentou uma solução semelhante:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: