Flower Vases
Time limit6sMemory limit128 MB
Given two pairs of pentominoes, decide whether each pair can be joined edge to edge into the same ten-square outline.
- Level
Medium5 of 10
- Topics
- Brute force, Geometry
- Solved
- No attempts yet
Problem
Junkyu is throwing a garden party at his house this weekend. A lot of friends are coming, so he wants to show off the gardening knowledge he has been quietly building up. One wide path runs through his garden, and before the guests arrive he plans to line both sides of it with flower vases. One side gets pale tan flowers, the other gets flowers in a dark pastel red, and every vase is the same color as the flowers in it.
Repainting all of the vases he already owns before the weekend would take too long, so Junkyu decided to buy new ones. While looking around he found a Dutch company that makes vases in whatever color he asks for and guarantees delivery by that same afternoon, and he ordered on the spot. The company sells pentomino-shaped vases, designed with great care so that they stand upright whichever way you set them down.
A pentomino is five unit squares joined together so that two touching squares always meet along a whole edge. There are only 12 different pentominoes, drawn below, and each one is named after the letter it resembles most.
F I L N P T
.## ##### #. .# ## ###
##. #. .# ## .#.
.#. #. ## #. .#.
## #.
U V W X Y Z
#.# #.. #.. .#. .# ##.
### #.. ##. ### ## .#.
### .## .#. .# .##
.#
All 12 shapes have the same area, five unit squares. A vase can be rotated and flipped freely, so shapes that coincide after a rotation or a reflection count as the same shape.
Junkyu buys two yellow vases and two red vases, then puts the two yellow vases on one side of the path and the two red vases on the other side. He knows his aesthetics, so he wants the outline formed by the two vases on one side to look exactly like the outline formed by the two vases on the other side. Seen from the front they may not overlap in a way that loses area, and the two vases on the same side are pushed together until the seam between them is invisible, so only the outline has to match. The two vases on one side therefore meet along at least one whole edge and form a single connected figure.
Some combinations can never give the same outline, one side holding W and F while the other holds I and I for one. Junkyu has no plan to pick such a combination, but he does not want to miss one like P and U on one side against V and Z on the other, which looks like a mismatch until you place the pieces properly. That is why he asked you for a program.
Given the shapes of the two yellow vases and the shapes of the two red vases, decide whether they can be arranged so that the two outlines are the same.
Input
The input consists of several test cases.
Each test case is a single line. It gives the shapes of the two yellow vases as a two-letter string, then the shapes of the two red vases as a two-letter string, separated by a space. Every shape is an uppercase letter and is one of the 12 shapes above. The input ends at end of file.
Output
For each test case, print one line: YES if the two yellow vases and the two red vases can be arranged so that their outlines are the same, and NO if no arrangement makes them the same.