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 is some observations to share.
Could anyone help me to solve this?