Don Miguel places a token in one of the $(n+1)^2$ vertices determined by an $n \times n$ board. A [i]move[/i] 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 [i]path[/i] 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?
1. **Reformulating the Problem:**
   We need to find the maximum number of diagonal moves (length $\sqrt{2}$) in a path that visits each of the $(n+1)^2$ vertices of an $n \times n$ board exactly once. A move is valid if it stays within the board and moves to an adjacent vertex.

2. **Path Length:**
   The total number of moves in the path is $(n+1)^2 - 1 = n^2 + 2n$.

3. **Case 1: \( n \) is even**
   - Let \( n = 2k \).
   - Color the vertices of the board in a checkerboard pattern: a vertex \((x, y)\) is black if \(x + y\) is even and white if \(x + y\) is odd.
   - Define a black vertex \((x, y)\) as **wangy** if \(x\) is even and **tangy** if \(x\) is odd.
   - Notice that wangy vertices outnumber tangy vertices by exactly \(2k + 1\).

4. **String Representation:**
   - Associate a string of length \((n+1)^2\) with characters \(B\) and \(W\) to the path, where \(B\) represents a black vertex and \(W\) represents a white vertex.
   - The number of side moves (cardinal directions) is equal to the number of color changes in the string.

5. **Counting \(B\)-blocks:**
   - A **$B$-block** is a contiguous sequence of \(B\)'s in the string.
   - Each \(B\)-block can have at most one more wangy than tangy vertices.
   - Since wangy vertices outnumber tangy vertices by \(2k + 1\), there are at least \(2k + 1\) \(B\)-blocks.
   - This implies at least \(2 \cdot (2k + 1 - 1) = 4k\) color changes, corresponding to at least \(4k\) side moves.

6. **Maximum Diagonal Moves:**
   - The total number of moves is \(n^2 + 2n\).
   - The number of side moves is at least \(4k\).
   - Therefore, the number of diagonal moves is at most \(n^2 + 2n - 4k = n^2\).

7. **Case 2: \( n \) is odd**
   - Let \( n = 2k + 1 \).
   - Color the vertices similarly in a checkerboard pattern.
   - Define \(B\)-blocks and \(W\)-blocks analogously.

8. **Counting \(W\)-blocks:**
   - There must be at least \(\frac{n+1}{2}\) \(W\)-blocks.
   - Similarly, there must be at least \(\frac{n+1}{2}\) \(B\)-blocks.
   - This implies at least \(2 \cdot \frac{n+1}{2} - 1 = n\) color changes, corresponding to at least \(n\) side moves.

9. **Maximum Diagonal Moves:**
   - The total number of moves is \(n^2 + 2n\).
   - The number of side moves is at least \(n\).
   - Therefore, the number of diagonal moves is at most \(n^2 + 2n - n = n^2 + n\).

10. **Conclusion:**
    - For even \(n\), the maximum number of diagonal moves is \(n^2\).
    - For odd \(n\), the maximum number of diagonal moves is \(n^2 + n\).

\(\blacksquare\)

The final answer is \( \boxed{ n^2 } \) if \(n\) is even and \(n^2 + n\) if \(n\) is odd.