TileMatch

TCCC '03 Round 4 · 2003-03-12 · by dgoodman

TCCC '03 Round 4 · 2003-03-12 · by dgoodman · Brute Force, Simple Search, Iteration

Show categories

Class Name: TileMatch

Return Type: int

Method Name: uncolor

Arg Types: (vector<string>)

Problem Statement

A square n by n tile has n^2 one by one cells, some of which are colored. A number of identical tiles will be laid in a rectangular format, with the corner of each tile coinciding with the corners of three other tiles. The tiles will not be laid upside down.

 Legal Format        Illegal Format 
 
_|___|___|___|_        _|   |___|   |_
 |   |   |   |          |___|   |___|
_|___|___|___|_        _|   |___|   |_
 |   |   |   |          |___|   |___|
_|___|___|___|_        _|   |___|   |_
 |   |   |   |          |   |   |   |

We say that a tile has the "edge-crossing" property if, no matter how the tiles are rotated when they are laid, every colored cell on the edge of one tile is adjacent (orthogonally or diagonally) to at least one colored cell on another tile. This is a desirable property since it helps to hide tile edges.

This picture shows 3 by 3 tiles, with the colored cells indicated by 'X' and the uncolored cells by ' '. Note that all the tiles have the same coloring pattern but that each tile can be laid in any of four possible rotations.

 |   |   |   |
-|---|---|---|-
 |XX | X | XX|
 |XXX|XX | XX|
 |   |XX | X |
-|---|---|---|-
 |   |   |   |

Create a class TileMatch that contains the method uncolor that takes a String[] giving the original pattern of colored cells on a tile as input and returns the minimum number of cells that we need to uncolor to give the tile the "edge-crossing" property.

pattern is a square collection of '-', denoting an uncolored cell, and 'X', denoting a colored cell. Each element of pattern gives the coloring of one row.

Notes

A colored cell on the edge of a tile must be uncolored if there is some way to rotate and arrange tiles so that the colored cell is not adjacent to any colored cells on an adjacent tile (vertically, horizontally, or diagonally).
Some cells, which need not be uncolored at first, may have to be uncolored after some other cell is uncolored. See example 4.

Constraints

pattern contains between 2 and 50 elements, inclusive
the length of each string in pattern is the same as the number of strings in pattern
each character in each element of pattern is either '-' or 'X'

Examples

{"XXX",
 "XXX",
 "---"}
Returns: 5

Since the adjacent tiles may all be oriented so the adjacent edges have no color, you must uncolor all the edge cells. Leave the center cell colored -- you can always leave a cell colored when it is not on the edge of a tile.

{"XXX",
 "XXX",
 "-X-"}
Returns: 0

Every adjacent tile will have a colored cell in the middle of each edge, and this will be adjacent to every cell in the edge.

{"XXXX",
 "XXXX",
 "-X--",
 "XX--"}
Returns: 3

It is necessary to remove the color from the 3 colored corner cells. This gives the following tile with the "edge-crossing" property: -XX- XXXX -X-- -X--

{"-X","X-"}
Returns: 0

{"X-XX---XX-","X-XX---XX-","X-XX---XX-","X-XX---XX-","X-XX---XX-","X-XX---XX-","X-XX---XX-","X-XX---XX-","X-XX---XX-","X-XX---XX-"}
Returns: 18

{"XXX","XXX","---"}
Returns: 5

XXX XXX --- Since the adjacent tiles may all be oriented so the adjacent edges have no color, you must uncolor all the edge cells. Leave the center cell colored -- you can always leave a cell colored when it is not on the edge of a tile.

10)

{"-XX-",
 "XXXX",
 "XXXX",
 "---X"}
Returns: 7

We end up having to uncolor all of the colored cells on the edge.

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

Coding Area

Language: C++17 · define a public class TileMatch with a public method int uncolor(vector<string> pattern) · 23 test cases · 2 s / 256 MB per case