TopCoder problem "TileMatch" used in TCCC '03 Round 4 (Division I Level Two)



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.

 

Definition

    
Class:TileMatch
Method:uncolor
Parameters:String[]
Returns:int
Method signature:int uncolor(String[] pattern)
(be sure your method is public)
    
 

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

0)
    
{"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.
1)
    
{"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.
2)
    
{"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--
3)
    
{"XX--",
 "---X",
 "X---",
 "--X-"}
Returns: 0
4)
    
{"-XX-",
 "XXXX",
 "XXXX",
 "---X"}
Returns: 7
We end up having to uncolor all of the colored cells on the edge.
5)
    
{"---X--",
 "-----X",
 "------",
 "------",
 "X-----",
 "----X-"}
Returns: 4
6)
    
{"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXX-",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XX--X-X-XX-XX-XXXXX-X-XXX-X-X--XXXXXXXXXXXXXXXXXXX",
 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}
Returns: 170

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1270

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4482&pm=1270

Writer:

dgoodman

Testers:

lbackstrom , brett1479 , schveiguy

Problem categories:

Brute Force, Simple Search, Iteration