It's easy to give constructions for $2 \times k$ boards or $m \times n$ boards where $m,n$ are even. If a board has more than two odd rows/columns, then there exists an odd row/column such that the rook neither finishes nor starts on it. Then each time the rook enters the row/column, it covers two squares then leaves, so the row/column has an even number of squares, contradiction.

Consider a bipartite graph $G(m,n)$ with one partite as rows and the other as columns. Then the problem is equivalent to having a semi-eulerian path. Hence, $(m,n)=(2,n),(m,2),(2k,2l)$ for any $m,k,l$.

Solved with GEPASSUP. Rook can travel each square if and only if $(m,n)=(1,1),(2,n),(m,2),(2k,2l)$. Construction: Let $(i,j)$ be $i.$ row and $j$ column. If $(m,n)=(2,n),(n,2)$ we see that \[(1,1)\rightarrow(1,2)\rightarrow (2,2)\rightarrow (2,1)\rightarrow (3,1)\rightarrow \dots \]Passes through each square once. Let's give an example for $(2k,2l)$. \[(1,1)\rightarrow (2k,1)\rightarrow (2,2k)\rightarrow (2,2k-1)\rightarrow (1,2k-1)\rightarrow \dots (2,1)\rightarrow (2,2)\rightarrow (1,2)\rightarrow (1,3)\]And we apply the same for $(2k-2)\times (2l)$.$\square$ Proof: Suppose that $m,n\geq 3$. Choose a row/column $S$ which does not contain the start or end point (WLOG assume that $S$ is a column). When the rook enters into $S$ from another column, then it must move to a square in $S$ and then it leaves the column. Hence we can pair the squares bijectively in $S$ hence $S$ contains an even number of squares as desired.$\blacksquare$

Attachments: