Neste problema, temos um mapa lunar de dimensão máxima 20x20 quadrículas e um conjunto de N (<= 50) crateras. As crateras são círculos e são-nos fornecidas as coordenadas do seu centro e raio. Uma quadrícula considera-se dentro da cratera se o centro da quadrícula estiver contido no circulo.
Disto isto, o objectivo é determinar qual é a maior linha horizontal e vertical de quadrículas não abrangidas pelas crateras.
Análise
A dificuldade maior do problema é determinar quais são as quadrículas do mapa abrangidas pelas crateras, mas este problema requer uma implementação cuidada.
As coordenadas começam em zero, por isso, o centro da quadrícula do canto inferior esquerdo é (0.5, 0.5). Para saber se uma quadrícula pertence a um círculo, podemos usar a equação do círculo (x-x0)2 + (y-y0)2 <= r2.
Deste modo, podemos transformar o mapa dado, numa matriz de zeros e uns como demonstrado na figura seguinte.
Como a dimensão máxima do mapa é de apenas 400 quadrículas, podemos testar cada quadrícula face a cada uma das 50 crateras sem problemas em termos de tempo de execução.
As crateras podem ter centros em coordenadas negativas, mas isso não é relevante desde que usemos a equação do circulo.
Depois de construirmos a matriz, basta-nos procurar as maiores sequências contíguas de zeros.
O problema parece muito simples mas há vários sítios onde nos podemos enganar, incluindo nos desempates em caso de linhas de dimensão igual. Se bem me lembro, a esmagadora maioria dos concorrentes (eu incluído) teve zero pontos neste problema.
Sem comentários:
Enviar um comentário