1087 - Dama
Um problema que envolve um raciocínio bem legal.
Last updated
Was this helpful?
Um problema que envolve um raciocínio bem legal.
Last updated
Was this helpful?
Primeiramente, vamos provar que é possível ir de uma casa até qualquer outra casa do tabuleiro com no máximo dois movimentos. Considere a origem com as coordenadas (x1, y1) e o destino com as coordenadas (x2, y2). Os dois movimentos no máximo que você pode fazer com a rainha consistem em primeiro ir para (x2, y1) e depois ir para (x2, y2).
A partir daí, podemos economizar uma viagem se pudermos ir direto para (x2, y2) usando os movimentos possíveis da rainha, o que pode acontecer em três casos diferentes:
Os pontos de origem e destino estão na mesma linha, ou seja, x1 = x2;
Os pontos de origem e destino estão na mesma coluna, ou seja, y1 = y2;
Os pontos de origem e destino estão na mesma diagonal, ou seja, |x1 - x2| = |y1 - y2| (a diferença entre as distâncias horizontal e vertical são iguais).
Lembrando que quando x1 = x2 e y1 = y2, não é necessário fazer movimento algum.