Solução escrita por Vitor Veiga
Conhecimento prévio necessário:
Resumindo o problema, temos duas posições $$(a, b)$$ e $$(c, d)$$ representadas em um eixo cartesiano e queremos o menor número possível de movimentos dos tipos $$(x, y) \rightarrow (x + 1, y + 1)$$ ou $$(x, y) \rightarrow (x – 1, y)$$ (vai uma casa para nordeste ou para oeste) para ir da primeira até a segunda posição.
Dessa forma, vamos dividir o problema em duas partes. Primeiro temos que garantir que, no eixo y, Andremfq não está acima da medalha, pois é impossível ir para baixo no eixo y. Cumprindo essa condição, vamos calcular quantos movimentos do tipo 1 $$(x + 1, y+1)$$ são necessários para chegar na ordenada da medalha, $$d – b$$.
Depois, Andremfq estará na posição $$(a + (d – b), d)$$ que, para que seja possível chegar no destino, não pode estar à esquerda da medalha, pois caso ele realizasse um movimento do tipo 1, indo para a direita, ele também estaria saindo da ordenada da medalha, sem possibilidade de voltar. Então calculamos quantos movimentos $$(x – 1, y)$$ ele deve fazer para chegar na medalha, $$a + (d – b) – c$$.
Retornamos então o número total de movimentos $$(d – b) + a + (d – b) – c = a – 2b – c + 2d$$. Segue o passo a passo do segundo caso teste:
Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.