Triple Town
Student Xiaoxi has recently become fond of the iOS game "Triple Town". In his spare time, Xiaoxi has been thinking about how to achieve a high score in this game.
As shown in Figure 1, the game is played on an $n \times m$ map. The game provides a construction sequence, and the player must choose empty locations to build the corresponding building units according to the sequence. There are nine different levels of buildings, ranging from low to high: Grass, Bush, Tree, Hut, etc. (for convenience, we will refer to them as $L_1, L_2, L_3, \dots, L_9$).
Figure 1
After a player builds a unit in an empty location, it may trigger a reaction. The condition for a reaction is: starting from this cell, if the size of the connected component formed by cells with the same building level as this unit is greater than or equal to 3, then this connected component will be merged into a building of the next level. The location of the new building will be the location of the last built unit, and the other locations in the connected component will become empty again. Here, a connected component refers to a set of locations that are directly or indirectly adjacent. It should also be noted that $L_9$ is the highest level of building, so multiple $L_9$ connected components will not merge. For example, in Figure 2, after building the middle $L_1$, the $L_1$ units connected to that location are merged into an $L_2$.
Figure 2
Note that during the merging process, it may trigger a chain reaction, as shown in the figure below.
Figure 3
The score in the game depends on the units built by the player and those formed by reactions. Building or forming a building unit earns the corresponding points. The scoring table for different levels of buildings is as follows:
| Building | $L_1$ | $L_2$ | $L_3$ | $L_4$ | $L_5$ | $L_6$ | $L_7$ | $L_8$ | $L_9$ |
|---|---|---|---|---|---|---|---|---|---|
| Points | 4 | 20 | 100 | 500 | 1,500 | 5,000 | 20,000 | 100,000 | 500,000 |
Taking the two game processes just mentioned as examples: In Figure 2, first $L_1$ was built, earning 4 points; subsequently, $L_1$ reacted to form $L_2$, earning another 20 points. The total score is 24. In Figure 3, the score for this operation is $4+20+100+500=624$ points.
To reduce the difficulty of the game, the game also provides two types of items: "Star" and "Bomber". At the beginning of the game, the player is given $p$ Star items and $q$ Bomber items, which the player can use at any time. Their functions are as follows:
- "Star" item: Can be placed in an empty location. When placed, the Star will automatically become the highest-level building that can trigger a reaction. If no reaction can be triggered at that location, it becomes $L_1$. For example, in Figure 3, placing a Star in the middle position automatically turns it into $L_3$. The score is calculated based on the building after the transformation.
- "Bomber" item: Can be placed on a location with a building, acting on that building and restoring the location to empty. When using a Bomber, the score will be deducted by half the points of the destroyed building (i.e., the score is negative).
During the game, the player must build according to the given sequence, but can use the two items at any time. The goal of the game is to achieve the highest score through reasonable operations.
Input
This is an answer-submission problem. The input files tritown1.in through tritown10.in are provided in the problem directory.
For each test case, the first line of the input file contains two integers $n, m$, representing that the map contains $n$ rows and $m$ columns.
The next line contains two integers $p, q$, representing the number of Star items and Bomber items, respectively.
The next $n$ lines contain the $n \times m$ initial map. The character "." represents an empty space, and the digits 1~9 represent buildings of the corresponding levels.
The next line contains an integer $k$, representing the length of the construction sequence.
The last line contains $k$ integers between 1 and 9 separated by spaces, representing the contents of the construction sequence.
Output
For the 10 given input files tritown1.in~tritown10.in, you need to submit your output files tritown1.out~tritown10.out respectively.
The output file contains the commands for the player to play the game, with a total of 4 types of commands:
| Command | Meaning |
|---|---|
PUT x y |
Place the next unit in the construction sequence into the empty space at row $x$, column $y$. |
STAR x y |
Place a Star item into the empty space at row $x$, column $y$. |
BOMBER x y |
Place a Bomber at row $x$, column $y$; this location must not be empty. |
END |
End the game and calculate the current score. |
The output must end with the END command. The player can end the game at any time.
Examples
Input 1
2 3 1 1 ..1 221 2 1 3
Output 1
PUT 1 2 PUT 1 1 STAR 2 1 END
Note 1
The score for the first step is $4+20+100=124$; The score for the second step is 100; The score for the third step is $100+500=600$; The total game score is $124+100+600=824$ points.
Subtasks
For each test case, we have set 9 scoring parameters $a_{10}, a_9, \dots, a_2$. If the player's output is invalid, the score is zero. Otherwise, let the game score in your solution be $w_{user}$. Your score will be given by the following table:
| Score | Condition | Score | Condition |
|---|---|---|---|
| 10 | $w_{user} \ge a_{10}$ | 5 | $w_{user} \ge a_5$ |
| 9 | $w_{user} \ge a_9$ | 4 | $w_{user} \ge a_4$ |
| 8 | $w_{user} \ge a_8$ | 3 | $w_{user} \ge a_3$ |
| 7 | $w_{user} \ge a_7$ | 2 | $w_{user} \ge a_2$ |
| 6 | $w_{user} \ge a_6$ | 1 | $w_{user} > 0$ |
If multiple conditions are met, the highest score among the met conditions is taken.
Implementation Details
We provide a tool called checker to test whether your output file is acceptable. The method to use this tool is to run it in the terminal:
./checker <case_no>
After you call this program, checker will provide the test results based on the output file you provided, which include:
- Abnormal exit: Unknown error;
- Output File Do Not Exist: Output file not found;
- Output Invalid!: The output file is incorrect, and it may contain specific error information;
- Correct! Your score is x: The output is acceptable, and your score is $x$.
Note
Please keep the input files tritown*.in and your output files tritown*.out safe and make backups to avoid accidental deletion.