OIM

Don Miguel coloca una ficha en alguno de los $(n+1)^2$ vértices determinados por un tablero de $n \times n$. Una jugada consiste en mover la ficha desde el vértice en el que se encuentra a un vértice adyacente en alguna de las ocho posibles direcciones: $\uparrow, \downarrow, \rightarrow, \leftarrow, \nearrow, \searrow, \swarrow, \nwarrow$, siempre y cuando no se salga del tablero. Un recorrido es una sucesión de jugadas tal que la ficha estuvo en cada uno de los $(n+1)^2$ vértices exactamente una vez. ¿Cuál es la mayor cantidad de jugadas diagonales ($\nearrow, \searrow, \swarrow, \nwarrow$) que en total puede tener el recorrido?