I have a problem with the following task:
On a chessboard N x N M white pawns were placed. The black king is at (0,0) (upper left corner) and has to reach (n-1,n-1)(lower right corner). During his tour, the king must capture all the pawns.
The case of check can be ignored. What is the minimum of King’s moves?
Time limit: 10sec.
Memory limit: 60MB
N - length of side of chessboard
M - number of pawns
Then M coordinates of pawns
e.g. For input:
It seems to be a problem of traveling salesman but i think it can be solved much faster. I was thinking about something similar to Kruskal. I would be grateful if anyone solved/gave hint to solve this problem.