In a n x m chessboard with cells labeled (i, j) for 1 ≤ i ≤ N, 1 ≤ j ≤ M, there is a stone at (1, 1). A and B is playing a game.
A starts first, and they alternately move stone to adjacent cell (north / west / south / east). It's okay to move stones to previously visited cells, but it's prohibited to move stones to previously visited "edges". For example, if someone wants to move stone from (1, 1) -> (1, 2), they shouldn't have a record of visiting (1, 1) / (1, 2) or (1, 2) / (1, 1) cells consecutively. Player unable to make a move loses.
Who is the winner? 1 ≤ n, m ≤ 106
About 1 month ago, me and other guys tried to solve this problem but failed. I also googled about this problem, but wasn't able to find any resources about it :/ Here are some observations to share.
If min(N, M) = 1, then the answer is determined by parity.
If both N, M is odd, then player B wins. B can simply imitate A
If N = M, then player B wins. B can push A to (k, k) cell in whatever case.
Then maybe it is about the parity? But according to some handwork, I'm not sure..
- If N = 2, M = 1, A wins.
- If N = 2, M = 2, B wins.
- If N = 2, M = 3, A wins.
- If N = 2, M = 4, A wins.
- If N = 2, M = 5, B wins.
Could anyone help me to solve this?