Блог пользователя purist

Find All reachable squares for a knight on chessboard in K moves when opponent has another knight.
Автор purist, история, 6 лет назад, По-английски

Given an NxM chessboard, you have a knight at some position and your opponent also has a knight, Find number of squares reachable to your knight in exactly K moves without being captured by opponent.There is no other piece other than 2 knights mentioned. You move first. Both players play optimally. Obvious solution would be to recursively try out each possibility for both knights but that would be too slow. Is there deterministic polynomial time solution ?

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can store, for each number of moves, all squares your knight can occupy and all squares for the other one as well.

For example, before the first move, your knight can only be at it's initial position.

This can lead to an O(K(NxM)2) algorithm.

→ Ответить