PlusSign | Topcoder Archive

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.

Definition

Class:: PlusSign
Method:: draw
Parameters:: String[]
Returns:: int
Method signature:: int draw(String[] pixels)
(be sure your method is public)

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

```
{".#..",
 "#.#.",
 ".#..",
 "...."}
```
```
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.
```
{"..#....",
 ".......",
 "......#",
 ".......",
 ".......",
 ".......",
 "......."}
```
```
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.
```
{"#..",
 "...",
 "..."}
```
```
Returns: -1
```
No valid plus sign that would fit into this grid can include the given black pixel.

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)2024, Topcoder, Inc. All rights reserved.