
69  ZOJ Monthly, August 2008  1007
There's a game named Puzzle Quest and watashi loves it so much. The Battle Grid of this game is the main part of the game. The Battle Grid is an N x M (1 <= N, M <= 8) grids that holds Blue(B), Green(G), Red(R) and Yellow(Y) Mana Gems, Skulls(O), Stars(P), Gold Coins(M). The battle takes place by connecting groups of 3, 4 or 5 of these items in order to clear up the Battle Grid.
When any items on the Battle Grid are matched up in a 3, 4 or 5 of a kind in a row or in a line, they disappear from the grids and all the gems above them fall down to replace the empty areas they left in the grids. If 3, 4, 5inarow appears after falling down, they will disappear from the grids recursively. Each move is valid if it matches up at least 3 items of a kind in a row. Once you have purchased the Dungeon for your hero's Citadel, you are able to attempt to capture enemies if you finish the Capture puzzle. When you encounter an enemy that you have defeated at least 3 times, the Capture puzzle will appear. Capture puzzles take place on the Battle Grid and inherit the same rules as a typical battle. Instead, you are given a specific pattern of mana gems, skulls, stars and gold coins. The goal is to clear the screen of all items in the grids. watashi would like to capture all the enemies, but the Capture puzzles are so hard for watashi. Can you help him? Input The first line of the input block contains the numbers N, M (1 <= N, M <= 8). The 2 ~ N + 1 line will each contain M characters. 'B' for Blue, 'G' for Green, 'R' for Red and 'Y' for Yellow, 'O' for Skulls, 'P' for Stars, 'M' for Gold Coins, and ' ' (space) for empty grid. There will be one separate line between two consecutive input blocks. There will be no more than 25 test cases. In each test case, it is guaranteed that there will be no nonempty grid above any empty grid. Output The first line of your output block should be a single integer K represent the number of moves in your solution. The 1 ~ K + 1 line will contain your move description (each move must be valid). Each move description must be in the form: "x y direction". (x, y) should be the grid you move (the upperleft grid is (0, 0)) and the direction is one of ("up", "down", "left", "right"). If there are more than one solution, output any one of them. Each output block is followed by a separate line. You can assume that each Puzzle Grid has at least one solution. Sample Input 1 4 OO O 4 8 MMP RRMRR PPRPPR Sample Output 1 0 3 left 3 1 2 down 3 5 up 2 2 down Hint1 Sometimes you can regard the empty grid as a virtual item, like follow: 4 5 BB BB OO OO MM MM PPMPPyou can move (1,1) to the right and the puzzle will become 4 5 B OB BB MM MM PPMPP Hint2 When two or more 3,4,5inrows appears at the same time, they will disappear simultaneously. (1) 4 2 RB BR BR OOafter move (0,0) to the right , the puzzle change into 4 2 OO(2) 3 4 RROR PPRO MMROafter move (0,3) to the left , the puzzle become 3 4 PP MM Author: OUYANG, Jialin 