Connection Status:
Competition Arena > Puzzle58

Puzzle58

SRM 698 (Google) · 2016-08-27 · by cgy4ever

SRM 698 (Google) · 2016-08-27 · by cgy4ever · Graph Theory
Class Name: Puzzle58
Return Type: String
Method Name: getAnswer
Arg Types: (vector<string>, vector<int>, vector<int>)
Problem Statement

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.

Constraints

  • 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].
Examples
0)
{"..#.#.",
 "..#..#",
 "..#..."}
{1,1}
{0,4}
Returns: "CL"

The only solution is: 00#1#. .0#1.# 00#111

1)
{"....",
 "#..#",
 "....",
 "...."}
{1,2}
{1,2}
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?".

2)
{"...",
 "...",
 "..."}
{1,1}
{1,1}
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.

3)
{"......",
 "......",
 "......",
 "......",
 "......",
 "......"}
{1,2,4,3,1,4}
{1,1,1,2,4,4}
Returns: "?CLL??"
4)
{"...",
 "...",
 "..."}
{0}
{0}
Returns: "Impossible"

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

Coding Area

Language: C++17 · define a public class Puzzle58 with a public method string getAnswer(vector<string> board, vector<int> row, vector<int> col) · 92 test cases · 2 s / 256 MB per case

Submitting as anonymous