I'm stuck in this problem for a while now.(It reminded me with the "Berzerk" problem here)
To be honest; I never really understood this kind of problems nor did I ever understand why a solution is always possible(When the author says so).
When I think of it(or any similar problem) I always believe that it will go on forever..
Specially when the statement says; "If both the players play clever and cautious(or optimally)..
When I read the examples, an idea crossed my mind; the player will win if and only if he can get to the north-east,north-west,south-east,south-west cell of his opponent's.
However, I don't know whether that is the only possibility.
Please note that I don't need help with the first two subtasks which are: R=2 & C=2 and R <= 100 & C=1.
The real problem is with the other two subtasks: R,C <= 100 and R,C <= 1e9 ...