Connection Status:
Competition Arena > PlusSign

PlusSign

TCO17 Austin · 2017-03-31 · by Nickolas

TCO17 Austin · 2017-03-31 · by Nickolas · Brute Force
Class Name: PlusSign
Return Type: int
Method Name: draw
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are given a String[] pixels that describes a rectangular bitmap. Each character in pixels represents one pixel of the bitmap: '#' is a black pixel and '.' is a white one.
A plus sign is a collection of black pixels that looks as follows:
  • The smallest bounding box of the collection of pixels is a square with an odd side length.
  • All pixels inside that bounding box are black (i.e., belong to the plus sign), except for four identical squares of white pixels - one in each corner of the bounding box.
  • The white squares must have a positive side length.
  • The side of the bounding box must be strictly greater than twice the side of each of the white squares.
Your task is to change the given rectangular bitmap into a bitmap on which all black pixels form a plus sign. To do this, you can only paint white pixels into black, but not in the other direction. (I.e., each of the pixels that are black in pixels has to remain black.)
Return the smallest number of pixels you have to paint black, or -1 if forming a plus sign is impossible.

Constraints

  • pixels will contain between 1 and 50 elements, inclusive.
  • Each element of pixels will contain between 1 and 50 characters, inclusive.
  • All elements of pixels will contain the same number of characters.
  • Each character in pixels will be '.' or '#'.
Examples
0)
{".#..",
 "#.#.",
 ".#..",
 "...."}
Returns: 1

It is sufficient to paint the pixel surrounded by the black pixels black to get a 3x3 plus sign with 1x1 cutouts in the corners.

1)
{"..#....",
 ".......",
 "......#",
 ".......",
 ".......",
 ".......",
 "......."}
Returns: 31

The smallest plus that can include these two black pixels is 7x7 with 2x2 cutouts in the corners, which requires painting 31 pixels black.

2)
{"#..",
 "...",
 "..."}
Returns: -1

No valid plus sign that would fit into this grid can include the given black pixel.

3)
{"..#.",
 ".###",
 "..#."}
Returns: 0

Don't need to paint any pixels.

4)
{".##.",
 "....",
 "....",
 "...."}
Returns: -1

Only a plus of even width is possible

13)
{"##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################"}
Returns: -1

Max # of black pixels with impossible answer

14)
{".################################################.", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 "##################################################", 
 ".################################################."}
Returns: -1

Still impossible (even width plus)

15)
{".###############################################..", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 "#################################################.", 
 ".###############################################..", 
 ".................................................."}
Returns: 0

Max # of black pixels with possible plus

16)
{".#################.#############################..", 
 "######.################################.#########.", 
 "############.####################################.", 
 "################################.################.", 
 ".################################################.", 
 "#######################.#############.###########.", 
 "######.##########################################.", 
 "############################.################.###.", 
 "#################################################.", 
 "##############.##################.###############.", 
 "####.############################################.", 
 "################################################..", 
 "#######..########################################.", 
 "######################.#################.########.", 
 "#################################################.", 
 "#################################################.", 
 "#########.####################.##################.", 
 "################.###########################.####.", 
 "###.#############################################.", 
 "#####################################.###########.", 
 "#########################.#######################.", 
 "##########.##############.#######################.", 
 "#################################################.", 
 "##############.########################.#########.", 
 "#################################################.", 
 "#################################################.", 
 "#########################.#######################.", 
 "#####.###########################...#############.", 
 "#################################################.", 
 "#################.########################.######.", 
 "#################################################.", 
 "##############################.##################.", 
 "###.#############################################.", 
 "################.###########################.####.", 
 "################.################################.", 
 "#########################.#######################.", 
 "######################################.##########.", 
 "#########.#######################################.", 
 "#################################################.", 
 "#############.######.########.#########.#########.", 
 "#################################################.", 
 "####.########################################.###.", 
 "##################################.##############.", 
 "###################################.#############.", 
 "##############.###########.#########..###########.", 
 "#################################################.", 
 "##.###############################.##############.", 
 "#.##########################################.####.", 
 ".###############.###############################..", 
 ".................................................."}
Returns: 62

Max possible plus with some cells missing

17)
{"..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 ".................................................#",
 "..#..............................................."}
Returns: 2395

Largest possible plus defined by 2 pixels (= max answer)

18)
{"..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "#.................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "........................#........................."}
Returns: 95

49x49 plus of width 1 (97 black cells total) defined by cells on adjacent arms

19)
{"..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "#.................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 ".........................#........................"}
Returns: 283

49x49 plus of width 3 (285 black cells total)

20)
{"..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 ".#...............................................#",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 ".................................................."}
Returns: 95

49x49 plus of width 1 (97 black cells total) defined by cells on opposite arms

24)
{"###.",
 ".#..",
 "...."}
Returns: -1

To catch off-by-one errors when checking whether the plus fits in the grid

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

Coding Area

Language: C++17 · define a public class PlusSign with a public method int draw(vector<string> pixels) · 66 test cases · 2 s / 256 MB per case

Submitting as anonymous