Hi everyone,
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?
1<=N<500
1<=M<50
Time limit: 10sec.
Memory limit: 60MB
Input:
N - length of side of chessboard
M - number of pawns
Then M coordinates of pawns
e.g. For input:
8
10
0 3
2 1
3 7
4 0
4 2
4 6
7 2
7 3
6 7
5 5
Output is:
21
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.