I had implemented a recursive solution for CAOS3 problem which obviously gave TLE for R>=12 and C>=12.
Could the A/C people share their strategies?
Did you use minimax or some other heuristics?
And do suggest a general strategy for approaching such game problems.
The standard way to solve such problems is by using Grundy numbers. You can read about it here:
(1) http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames
(2) http://sbjoshi.wordpress.com/tag/grundy-number/
Grundy number of a game state S is equal to mex(grundy number of all game states that are reachable from S in exactly one move).
In this problem, a possible move is to kill a monster at a certain position (i,j). Now, the game reduces to four independent games and hence, grundy number of the game resulting from this move is xor of grundy numbers of those four sub-games.
But aren’t grundy numbers used when you’re playing multiple games simultaneously or did u mean that the current problem can be reduced to that case?
When you select a monster, four new impartial games are created. Thus the XOR of the grundy numbers of these new games will be the grundy number of the initial game. The new games can be calculated again recursively. Dynamic programming can be used in this case.