LayeredGlass
SRM 770 · 2019-10-31 · by erinn
Problem Statement
You are working in a glass factory, that assembles layered glass, where two pieces of square glass are layered together to create a single, stronger pane of glass.
Unfortunately, the glass sometimes has defects... and a defect in either layer results in a defect to the finished product. However, as the pieces are square, they can be flipped and rotated in whatever way is optimal to minimize the number of defects in the finished product when the layers are put together.
The two pieces are glass are defined in
Return the minimum number of defective areas in the final layered product, assuming the two layers are rotated and flipped optimally.
Notes
- Both pieces of glass are square, that is, the number of strings in each array will be the same as the number of characters in each string.
Constraints
- a will have between 1 and 50 elements, inclusive.
- a and b will contain the same number of elements.
- a and b will both define a square.
- Each character of each element of a and b will be '.' or 'X'.
{"X.",
".."}
{"..",
".X"}
Returns: 1
Each layer has a defect, but if we rotate them properly, they line up, leaving only a single defect in the finished product.
{"...",
"..X",
"..."}
{"X..",
"...",
"..."}
Returns: 2
No matter what we do, both defects will appear separately in the finished product.
{"...",
"...",
"..."}
{"...",
".XX",
"..."}
Returns: 2
One layer of glass is perfect, but the other layer has two defects, regardless.
{".XX",
"...",
"..."}
{"X..",
"...",
"X.."}
Returns: 3
{"X.X",
".X.",
"X.X"}
{".X.",
"X.X",
".X."}
Returns: 9
{"XX..",
"X...",
"XX..",
"X..."}
{"XXXX",
"X.X.",
"....",
"...."}
Returns: 6
Note that you can also flip the panes, not just rotate them.
Submissions are judged against all 26 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LayeredGlass with a public method int minDefects(vector<string> a, vector<string> b) · 26 test cases · 2 s / 256 MB per case