We color the board with black and white in checkerboard pattern, with the bottom left being black. We show that the white ones are the only one working. First, we know that each step we take is from black to white or vise versa. So if you have an odd number of total squares, you must start with a square with the more abundant color. So in this case, if you cover one black, then black would become fewer than white, so you must start on white to travel through the entire board. But we're starting on black so it won't work. Now we induct down on both $n$ and $m$ to show that all blacks are possible. We can walk through an entire column or row and take the next column or row back, so that we can reach a $2m-2\times 2n$ or $2m\times 2n-2$ board. Also it's easy to check that in $2\times 4$ and $4\times 2$ boards all blacks are good. So we conclude that all blacks are possible.