Get Time

   Problem Statement  

 Problem Statement for Puzzle58

Problem Statement

    Puzzle58 is a single-player game. It is played on a rectangular board. Some cells on the board are blocked. You are given the layout of the board in the String[] board. Each character in board is either '.' (an empty cell) or '#' (a blocked cell).

A cell that is not on the border of the board has 8 neighbors. A Good shape is a shape formed by any 5 consecutive neighbors of a cell. All eight possible Good shapes are shown below. In each figure, 'o' denotes the central cell and 'x's denote the five cells that form the Good shape. (The cell denoted 'o' is not a part of the Good shape.)

There are four Good shapes of type 'C':

   xx    xxx    xx
   xo    xox    ox   xox
   xx           xx   xxx

Also, there are four Good shapes of type 'L':

   x     xxx   xxx     x
   xo    xo     ox    ox
   xxx   x       x   xxx

You are given the int[]s row and col. These describe a collection of cells: for each valid i, cell i has the coordinates (row[i], col[i]).

For each cell in the collection, you need to place a Good shape around the cell. The cells are not necessarily distinct. If a cell has multiple occurrences in the collection, each occurrence should have its own Good shape. There are several additional constraints:
  • All Good shapes must fully lie on the given board.
  • All Good shapes must be pairwise disjoint.
  • The Good shapes cannot contain any blocked cells.

If there is no valid way to place the Good shapes as required, return the string "Impossible". Otherwise, return a string that contains one character for each cell in the collection. For each i, character i of the return value should be:
  • 'C', if in all valid solutions the Good shape around cell i has type 'C'.
  • 'L', if in all valid solutions the Good shape around cell i has type 'L'.
  • '?' otherwise.


Parameters:String[], int[], int[]
Method signature:String getAnswer(String[] board, int[] row, int[] col)
(be sure your method is public)


-board will contain between 2 and 50 elements, inclusive.
-Each element of board will contain between 2 and 50 characters, inclusive.
-Each element of board will contain the same number of characters.
-Each character in board will be '#' or '.'.
-row will contain between 1 and 100 elements, inclusive.
-row and col will contain the same number of elements.
-Each element in row will be between 0 and n-1, inclusive, where n is the number of elements in board.
-Each element in col will be between 0 and m-1, inclusive, where m is the number of characters in board[0].


Returns: "CL"
The only solution is:

Returns: "L?"
There are two valid solutions, as shown below:

000.   000.
#10#   #.0#
.10.   .101
.111   .111

In both solutions the Good shape around cell 0 has type 'L'. However, the Good shape around cell 1 has type 'L' in one solution and type 'C' in the other. Hence, the correct return value is "L?".
Returns: "Impossible"
There is no way to put two disjoint Good shapes around the same cell: the cell has only 8 neighbors but the two shapes need 5+5 = 10 cells.
Returns: "?CLL??"
Returns: "Impossible"

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.

This problem was used for:
       Single Round Match 698 Sponsored by Google Round 1 - Division I, Level Three