1

I have a chess board N*M. Two "magical" knights are standing in random positions (x1,y1) and (x2,y2). They are magical, because they make moves simultaneously. The question is: "how many moves are required for them to meet (minimal amount)?"

As far as I understood if amount of moves for one knight to get into position of second is odd they won t meet otherwise divide by two the minimal path. But something tells me that I am wrong! Please help!)

enter image description here

Todor Markov
  • 2,869
Hmmman
  • 37
  • I assume you want a simpler way than running BFS to determine that. – Todor Markov Jan 30 '19 at 16:15
  • As far as I know BFS let you find the minimal path (amount of moves), but that s only a part of problem.
    Okay, consider simplier task, you have 1 knight standing F5 and second one standing H6. I m trying to make them meet, but it seems like it is impossible, because they are "magical")) Maybe there is a clever combination to make them meet?     – Hmmman Jan 30 '19 at 16:24
  • 1
    They will never meet if they start on different colored squares; this happens about half the time! – Dan Uznanski Jan 30 '19 at 16:25

1 Answers1

1

The knight can meet iff they start on a square of the same color. Each move each knight changes color, so if they start on different colors, they'll always be on different colors. And conversely, if they do start on the same color, any path from one knight to the other is even, so you can divide its length by 2.

Todor Markov
  • 2,869