Solução Informática Iniciante – Semana 52 – Problema 1

Solução por Lúcio Cardoso

A resposta para o problema é simplesmente $$max(|x_1-x_2|, |y_1-y_2|)$$.

Primeiro, note que a distância de $$(x_1, y_1)$$ para $$(x_2, y_2)$$ é $$|x_1-x_2|$$ $$+$$ $$|y_1-y_2|$$. Porém, como há a opção de mudar o valor de ambas as coordenadas do robô ao mesmo tempo, podemos fazer isto no máximo $$min(|x_1-x_2|, |y_1-y_2|)$$ vezes. Depois disso, teremos que mudar apenas o valor da primeira ou da segunda coordenada do robô, pois alguma das coordenadas do robô já será a mesma que a do destino. Isto é equivalente a andar $$max(|x_1-x_2|, |y_1-y_2|)$$ vezes.

A complexidade final é, então $$O(1)$$. Confira o código para melhor entendimento:

https://gist.github.com/luciocf/55f2cf915e6d3efd6a944ae13501f6be