PROBLEM STATEMENT
Like all other software engineers, Gogo likes to cut and eat cake. He used a rectangular baking
dish to make a cake. The dish is divided into a grid of unit square cells. Initially, all the
cells contained the cake.
Gogo's friend John wanted to eat the cake. Gogo gave John a rectangular cake cutter with the
following properties:
The cake cutter is divided into a grid of cells. The cells are of the same size as the cells of
the dish.
The cake cutter contains cells of two types: used cells and ignored cells.
Each of the first row, the last row, the first column, and the last column of the cutter contains
at least one used cell.
When used, the cake cutter must be placed on the dish according to the following rules:
Each cell of the cutter must contain a single cell of the dish.
It is not allowed to flip or rotate the cutter. Rows and columns of the cutter must correspond to
some consecutive rows and some consecutive columns of the dish in the given orientation. (See the
last two examples.)
Each used cell of the cutter must be placed onto a cell that still contains cake. The ignored
cells may be placed onto any cells.
When the cake cutter is used in the way described above, it removes the cake from all the used
cells. John may have used the cake cutter multiple times, one after another.
After John went home, Gogo examined the cake that remained in the dish. He now wants to check
whether John really cut the cake according to the above rules. You are given vector s cake
and cutter. The remaining cake is described by cake. More precisely, cake[i][j] is 'X' if the cell
in the i-th row and j-th column of the dish still contains cake; otherwise cake[i][j] is '.' (a
period). The cake cutter is described by cutter. More precisely, cutter[i][j] is '.' (a period) if
the cell in the i-th row and j-th column of the cutter is used, and 'X' if the cell is ignored.
Return "YES" (quotes for clarity) if it is possible that John only ate the cake by using the
cutter in the way described above. Return "NO" otherwise.
DEFINITION
Class:GogoXCake
Method:solve
Parameters:vector , vector
Returns:string
Method signature:string solve(vector cake, vector cutter)
NOTES
-The used cells in the cutter do not have to be contiguous.
CONSTRAINTS
-cake will contain between 1 and 50 elements, inclusive.
-Each element of cake will contain between 1 and 50 characters, inclusive.
-All elements of cake will contain the same number of characters.
-Each character in each element of cake will be either '.' or 'X'.
-There will be at least one '.' in cake
-cutter will contain between 1 and R elements, inclusive, where R is the number of elements in cake.
-Each element of cutter will contain between 1 and C characters, inclusive, where C is the number
of characters in each element of cake.
-All elements of cutter will contain the same number of characters.
-Each character in each element of cutter will be either '.' or 'X'.
-Each of the first row, the first column, the last row, and the last column of the cutter will
contain at least one '.'.
EXAMPLES
0)
{"X.X"
,"..."
,"..."
,"X.X"}
{".X"
,".."
,"X."}
Returns: "YES"
1)
{"..XX"
,"...X"
,"X..."
,"XX.."}
{".."
,".."}
Returns: "NO"
2)
{"...X..."}
{"..."}
Returns: "YES"
3)
{".X."
,"X.X"
,".X."}
{"."}
Returns: "YES"
4)
{"XXXXXXX"
,"X.....X"
,"X.....X"
,"X.....X"
,"XXXXXXX"}
{".X."
,"XXX"
,".X."}
Returns: "NO"
5)
{".."
,"X."
,".X"}
{".."
,".X"
,"X."}
Returns: "NO"
You may not flip the cutter.
6)
{"X.."
,".XX"
,".XX"}
{".XX"
,".XX"
,"X.."}
Returns: "NO"
You may not rotate the cutter.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.