XMarksTheSpot
SRM 700 · 2016-10-02 · by lg5293
Problem Statement
You are playing a treasure hunt game.
The game is played on a rectangular board that is divided into a grid of unit squares.
You are given the layout of the board in the
- 'O' (capital oh): This square contains a landmark.
- '.': This square is empty.
- '?': You do not know the contents of this square. It may contain a landmark and it may be empty.
A treasure is buried under one of the squares. You know something about its location:
- The row in which the treasure is buried is between T and B, inclusive, where T is the topmost row that contains a landmark and B is the bottommost row that contains a landmark.
- The column in which the treasure is buried is between L and R, inclusive, where L is the leftmost column that contains a landmark and R is the rightmost column that contains a landmark.
Thus, you can narrow your search space to a sub-rectangle of the original grid.
Suppose k is the number of grid squares which are unknown to you. In other words, let k be the number of '?' characters in board. There are 2^k different boards that correspond to the information you have. For each of those boards, compute the number of squares that may contain the treasure. Find and return the sum of those 2^k numbers.
Constraints
- board will have between 1 and 50 elements, inclusive.
- Each element of board will be the same length.
- Each element of board will have between 1 and 50 characters, inclusive.
- Each character of each element of board will be "O", ".", or "?".
- The number of "?" characters among all elements of board is at most 19.
- There will be at least one "O" character among all elements of board.
{
"?.",
".O"
}
Returns: 5
If the top left corner is empty, we only have 1 possible location of the treasure: the bottom right corner. If the top left corner is a landmark, the treasure can be anywhere in the grid: 4 possible locations. The return value is therefore 1 + 4 = 5.
{
"???",
"?O?",
"???"
}
Returns: 1952
{
"...?.",
"?....",
".O...",
"..?..",
"....?"
}
Returns: 221
{"OOOOOOOOOOOOOOOOOOOOO"}
Returns: 21
{"?????????OO??????????"}
Returns: 9963008
Submissions are judged against all 66 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class XMarksTheSpot with a public method int countArea(vector<string> board) · 66 test cases · 2 s / 256 MB per case