LaserTowersDiv1
SRM 627 · 2014-06-16 · by fsouza
Problem Statement
You are playing a strategy game on a rectangular board. The board is divided into a grid of unit square cells. Some of the cells are occupied by enemies. It is now your turn and you want to eliminate as many enemies as possible.
Some of the cells that are not occupied by enemy units contain your laser towers. Each laser tower is pointed in one of the four cardinal directions. The tower can target any single cell in its direction and eliminate all enemies in that cell. Note that the tower is tall and can target any cell in its direction, even if there are some enemies in cells that are closer than the target cell.
For each tower, you have to decide whether it is going to shoot or not. Then, you have to choose a valid target cell for each of the towers that is going to shoot. Finally, all selected towers shoot their lasers at the same time and they eliminate all enemies in their target cells.
You are also given two important pieces of information about the laser towers:
- For safety purposes, the towers were designed in such a way that no tower can target another tower. (You may assume that this is true in all test cases.)
- When you fire your laser towers, their laser beams are not allowed to cross, not even at their endpoints. That is, for each cell on the board there can be at most one laser tower that is shooting at or over that cell.
You are given a
- Empty cells are represented by the character '.' (period).
- Characters '1' through '9' represent cells that contain 1 through 9 enemy units.
- Characters 'A', 'V', '<', and '>' represent laser towers pointed north, south, west, and east, respectively.
Return the maximal total number of eliminated enemies.
Constraints
- board contains between 1 and 50 elements, inclusive.
- Each element of board contains between 1 and 50 characters, inclusive.
- All elements of board are of the same size.
- No tower is directed towards another one.
- Each character of the board is 'A', 'V', '<', '>', '.', or a digit between '1' and '9', inclusive.
{
".9",
">3",
".A"
}
Returns: 9
The lasers shouldn't cross (Even at their endpoints)
{
".......................9<>9.......................",
"......................99<>99......................",
".....................998<>899.....................",
"....................9988<>8899....................",
"...................99888<>88899...................",
"..................998887<>788899..................",
".................9988877<>7788899.................",
"................99888777<>77788899................",
"...............998887776<>677788899...............",
"..............9988877766<>6677788899..............",
".............99888777665<>56677788899.............",
"............998887776655<>556677788899............",
"...........9988877766555<>5556677788899...........",
"..........99888777665554<>45556677788899..........",
".........998887776655544<>445556677788899.........",
"........9988877766555444<>4445556677788899........",
".......99888777665554443<>34445556677788899.......",
"......998887776655544433<>334445556677788899......",
".....9988877766555444332<>2334445556677788899.....",
"....99888777665554443322<>22334445556677788899....",
"...998887776655544433222<>222334445556677788899...",
"..9988877766555444332221<>1222334445556677788899..",
".99888777665554443322211<>11222334445556677788899.",
"998887776655544433222111<>111222334445556677788899",
"AAAAAAAAAAAAAAAAAAAAAAAA..AAAAAAAAAAAAAAAAAAAAAAAA",
"VVVVVVVVVVVVVVVVVVVVVVVV..VVVVVVVVVVVVVVVVVVVVVVVV",
"998887776655544433222111<>111222334445556677788899",
".99888777665554443322211<>11222334445556677788899.",
"..9988877766555444332221<>1222334445556677788899..",
"...998887776655544433222<>222334445556677788899...",
"....99888777665554443322<>22334445556677788899....",
".....9988877766555444332<>2334445556677788899.....",
"......998887776655544433<>334445556677788899......",
".......99888777665554443<>34445556677788899.......",
"........9988877766555444<>4445556677788899........",
".........998887776655544<>445556677788899.........",
"..........99888777665554<>45556677788899..........",
"...........9988877766555<>5556677788899...........",
"............998887776655<>556677788899............",
".............99888777665<>56677788899.............",
"..............9988877766<>6677788899..............",
"...............998887776<>677788899...............",
"................99888777<>77788899................",
".................9988877<>7788899.................",
"..................998887<>788899..................",
"...................99888<>88899...................",
"....................9988<>8899....................",
".....................998<>899.....................",
"......................99<>99......................",
".......................9<>9......................."
}
Returns: 1296
One of the biggest maxflow inputs.
{
"..V..",
">.54.",
".>3.6",
"9..A."
}
Returns: 12
{
".9V.",
">..7",
".A1."
}
Returns: 10
{"."}
Returns: 0
Submissions are judged against all 90 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LaserTowersDiv1 with a public method int countMaxEnemies(vector<string> board) · 90 test cases · 2 s / 256 MB per case