OIM 2019 Problem 5

Don Miguel places a token in one of the $(n+1)^2$ vertices determined by an $n \times n$ board. A move consists of moving the token from the vertex on which it is placed to an adjacent vertex which is at most $\sqrt2$ away, as long as it stays on the board. A path is a sequence of moves such that the token was in each one of the $(n+1)^2$ vertices exactly once. What is the maximum number of diagonal moves (those of length $\sqrt2$ ) that a path can have in total?