Big limit Knight's tour problem

Revision en1, by Chi, 2018-10-22 16:20:33

It's the same knight's tour problem (since the problem is in Vietnamese i wont put a link to the original one):

We have a chessboard of size a*a, the knight's coordinate is x, y. We have to find the longest path of the knight (the maximum number of squares the knight can go through), without having the knight going through a same square twice. Note that it does not have to be a close tour. I used the recursion method (i do considered breaking the operation when there exist a path that covers all a*a squares, too) and finds out that it only works well for a <= 50 (however, occasionally is passes the time limit).

But the limit is fairly larger (a <= 500), which — of course, got me 3 TLEs (here)

So instead i just tried printing a*a, and the 3 tests that i got TLE verdict before now return AC, but its wrong for the other 7 tests. (here)

So lastly i tried this

    return 0;

and it got all AC for the 3 TLE tests but WA for 2 of the initially right ones (here)

Here's the code of the submission that got 70 points

Appreciate all helps.


  Rev. Lang. By When Δ Comment
en1 English Chi 2018-10-22 16:20:33 1306 Initial revision (published)