We claim that if there are even number of cells then Bob wins, and if there are odd number of cells then Alice wins.
To prove our claim we’ll present two optimal plays,
Even number of cells: Let’s call reverse move as making an 180 degree move to opponent’s move. That is if your opponent moves up, you move down and vice versa, if your opponent moves left, you move right and vice versa. Now if there are even number of cells then for each valid move by Alice there will exist a reverse move for Bob to make. So, Bob will always win if there are even number of cells.
Odd number of cells: Alice makes the first move to the longer dimension of the grid(any dimension if the grid is equal). After that starts to make reverse move to Bob. If reverse move is not allowed he should make the first allowed move while rotating in clockwise/anti-clockwise direction. This will ensure that Alice always wins.
Time Complexity: O(1)
Auxiliary Space: O(1)
