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

Solving the puzzle
Автор tom, история, 9 лет назад, По-английски

Hello Codeforces community,

Here is a problem: http://www.spoj.com/problems/SOLVING/

How would you solve it? I don't want to skew your view, so I just leave the question without mentioning my (apparently too slow) solution.

Thanks, tom

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

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

→ Ответить
»
9 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Did you try using A-Star algorithm? I think search space is too big even for this algorithm but you can give it a try. Since optimal solution is not required you may use non-consistent heuristic to speed up the search.

→ Ответить
  • »
    »
    9 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    Yes. My algorithm looks as follows:

    for every tile i from 1 to n*n-1
  go to tile i
  "bring" tile i near (manhattan distance <= 2) to the place it should be at
  run A* to put it there

    My heuristic is simple sum of manhattan distances between current point and destination point for tiles <= i.

    It works well except two last rows. Sometimes it takes a lot of time to finish them.

    → Ответить
»
9 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

My bad XDDDD, ignore, its stupid

→ Ответить