Collecting Coins |
In a maze of r rows and c columns, your task is to collect as many coins as possible.
Each square is either your start point ``S"(which will become empty after you leave), an empty square ``.", a coin square ``C" (which will become empty after you step on this square and thus collecting the coin), a rock square ``O" or an obstacle square ``X".
At each step, you can move one square to the up, down, left or right. You cannot leave the maze or enter an obstacle square, but you can push each rock at most once (i.e. You can treat a rock as an obstacle square after you push it).
To push a rock, you must stand next to it. You can only push the rock along the direction you're facing, into an neighboring empty square (you can't push it outside the maze, and you can't push it to a square containing a coin). For example, if the rock is to your immediate right, you can only push it to its right neighboring square.
Find the maximal number of coins you can collect.
3 3 4 S.OC ..O. .XCX 4 6 S.X.CC ..XOCC ...O.C ....XC 4 4 .SXC OO.C ..XX .CCC
1 6 3