GogoXCake

SRM 530 · 2011-11-22 · by dolphinigle

SRM 530 · 2011-11-22 · by dolphinigle · Greedy, Simulation

Show categories

Class Name: GogoXCake

Return Type: String

Method Name: solve

Arg Types: (vector<string>, vector<string>)

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 String[]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.

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

{"X.X"
,"..."
,"..."
,"X.X"}
{".X"
,".."
,"X."}
Returns: "YES"

{"..XX"
,"...X"
,"X..."
,"XX.."}
{".."
,".."}
Returns: "NO"

{"...X..."}
{"..."}
Returns: "YES"

{".X."
,"X.X"
,".X."}
{"."}
Returns: "YES"

{"XXXXXXX"
,"X.....X"
,"X.....X"
,"X.....X"
,"XXXXXXX"}
{".X."
,"XXX"
,".X."}
Returns: "NO"

172)

{".."
,"X."
,".X"}
{".."
,".X"
,"X."}
Returns: "NO"

You may not flip the cutter.

173)

{"X.."
,".XX"
,".XX"}
{".XX"
,".XX"
,"X.."}
Returns: "NO"

You may not rotate the cutter.

Submissions are judged against all 222 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GogoXCake with a public method string solve(vector<string> cake, vector<string> cutter) · 222 test cases · 2 s / 256 MB per case