Блог пользователя mohamed.gaber

knigtht's move
Автор mohamed.gaber, 13 лет назад, По-английски
we have an infinite chess board and we want to move from the position x1,y1 to the position x2,y2 using the minimum number of knight's moves.
I believe that this problem has a constant time solution but i couldn't approach it.
I would be grateful if any one explained the solution of this problem.
Thanks in advance.
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
This solution is technically constant time: go greedily (in O(1)) to some fixed neighborhood of x2,y2 (say, closer than 20 cells away), then find remaining route with BFS. The "constant" is quite large though. I think, BFS can be replaced with just some cases, which would look more like constant time solution.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    what is the greedy strategy to go to x2,y2 or how can i choose x2,y2.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Probably we need to consider some cases for greedy movement. Let x1=y1=0, x2>=0, y2>=0. If y2>2*x2, we need to make only [-1,+2] and [+1,+2] jumps. Otherwise we need only [+1,+2] and [+2,+1] jumps. We can approximately find how many jumps of each (of two) type we need using two linear equations.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
I have the following code which solves this problem in constant time but i couldn't understand how it works.

int64 dist(int64 x1, int64 y1, int64 x2, int64 y2)
{
    int64 dx = abs(x2-x1);
    int64 dy = abs(y2-y1);
    int64 lb=(dx+1)/2;
    lb = max(lb, (dy+1)/2);
    lb = max(lb, (dx+dy+2)/3);
    while ((lb%2)!=(dx+dy)%2) lb++;
    if (abs(dx)==1 && dy==0) return 3;
    if (abs(dy)==1 && dx==0) return 3;
    if (abs(dx)==2 && abs(dy)==2) return 4;
    return lb;
}
→ Ответить
  • 8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    here you go

    http://math.stackexchange.com/questions/1135683/minimum-number-of-steps-for-knight-in-chess
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Your solution it's fine...it´s simple math, read "Algorithmic problem solving book", or try with simple cases....
→ Ответить