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.