I have a matrix of size $N \times M$, There is a doll placed at $(1,1)$, which is the upper-left corner of the matrix. Two player makes an alternative turn.
If the doll is at $(x,y)$ then a player can move it to
$$ (x+1,y) \text{ or } (x-1,y) \text{ or } (x,y+1) \text{ or } (x,y-1) $$
only if the new place is not visited yet.
The one who can't make any move loses. Who will win?
My Approach: Since I can visit every place from $(1,1)$, so if $(N\cdot M)$ is odd then the second player wins; if it's even the first player wins.
Modification: If the doll is at $(x,y)$ then a player can move it to
$$ (x+1,y+1) \text{ or } (x-1,y-1) \text{ or } (x-1,y+1) \text { or } (x+1,y-1) $$ only if the new place is not visited yet.
Then who will win? Please, help me understand the two cases.
If $N\times M$ is even, then cover the board (matrix) with $2\times 1$ dominoes. Then the first player will move from one square of the domino to the next one. The second player will have to move into a new domino. The first players wins (always has an available move)
If $N\times M$ is odd, then cover the board with $2\times 1$ dominoes leaving $(1,1)$ not covered. Then the first player has to move into a domino, and the second player can move into the other square of the domino. The second player wins, having always an available move.
For the diagonal game it is the same, except that you have to look at coverings with "diagonal" dominoes, and approximately half of the squares are unused.
In the general case, if you know graph theory, you may take a look here.