Extended Bowling Alley#4064
Everyone is familiar with the game "Bowling," where the objective is to knock down pins using a ball. "Extended Bowling" shares this goal but introduces several innovations to make the game more challenging and engaging.
The playing field is a rectangular grid with cells horizontally and cells vertically. In each cell, except for those in the bottom row, one of the following objects can be placed:
a pin with a number on it;
a bomb;
a reflective switch;
a pit.
A ball is placed in one of the cells in the bottom row and can be launched upwards either vertically or at a 45° angle to the right or left. When the ball reaches the far left or far right cell of any row (except when moving vertically), it reverses the horizontal component of its movement vector. If the ball reaches a cell in the top row, it reverses the vertical component of its movement vector. The game ends when the ball reaches a cell in the bottom row.
When the ball encounters a cell containing an object, the following actions occur based on the object's type:
If the object is a pin, its number is added to the game's score, and the pin is removed from the field.
If the object is a bomb, it "explodes," destroying all objects in adjacent cells horizontally, vertically, or diagonally. If a reflective switch or pit is destroyed, the cell becomes empty. If a pin or bomb is destroyed, the same actions occur as when the ball hits a pin or bomb.
If the object is a reflective switch, the vertical component of the movement vector is reversed.
If the object is a pit, the ball stops moving, and the game ends.
If at any point the ball "loops" in a specific area of the field, the game ends.
Your task is to determine the maximum score achievable in the game, considering that the ball can initially be placed in any cell of the bottom row.
The first line contains two integers and , separated by a space, representing the size of the playing field horizontally and vertically (2 \leq nX \leq 100, 2 \leq nY \leq 100).
The second line contains an integer – the number of objects placed on the playing field (1 \leq N \leq nX \cdot (nY-1)).
The next lines describe each object with three elements , separated by spaces, where and are the object's coordinates (1 \leq oX \leq nX, 2 \leq oY \leq nY), and describes the object:
If the object is a pin, the number written on it (ranging from to );
If the object is a bomb, the symbol "*" (without quotes);
If the object is a reflective switch, the symbol "-" (without quotes);
If the object is a pit, the symbol "+" (without quotes).
All pairs , are unique.
The output should contain one integer – the maximum score that can be achieved in the game.
Example 1