## Wesley's Anger Contest 2 Problem 3 - Pumpkin Counting

View as PDF

Points: 15
Time limit: 1.0s
Java 2.5s
Python 4.5s
Memory limit: 1G

Authors:
Problem types

To celebrate Halloween, you have decided to hold an art contest! A drawing is a grid of pixels with rows and columns, composed of only # and . characters. # can be thought of as a black pixel, and . can be thought of as a white pixel. It is guaranteed that the drawing will be framed with a single layer of black pixels. For more details, refer to the input specification section.

As the head judge of this art contest, you have decided that the winner of the art contest will be the drawing with the most number of pumpkins. Given a drawing, can you count the number of pumpkins in it?

A pumpkin can come in various positive integer sizes. Specifically a pumpkin of size is a grid of pixels with rows and columns, composed of only #, ., and   characters. Here,   can be thought of as a transparent pixel. A pumpkin of size is considered to be in the drawing if there is a subgrid of the drawing with rows and columns such that every non transparent pixel in the pumpkin matches the pixel in the same row and column of the subgrid of the drawing.

A subgrid can be defined by integers . The rectangular region formed by all pixels that are in between rows and and columns and form the subgrid defined by .

The rows of pixels of a pumpkin of size are described below. Each row consists of pixels.

• The first row consists of (from left to right) transparent pixels, white pixels, and transparent pixels.
• The next rows each consists of transparent pixels, white pixel, black pixel, white pixel, and transparent pixels.
• The next row consists of white pixels, black pixel, and white pixels.
• The next rows each consists of white pixel, black pixels, and white pixel.
• The last row consists of white pixels.

Note that is the largest integer less than or equal to , and is the smallest integer greater than or equal to for a real number .

Below is a pumpkin of size .

      ...
.#.
.......#.......
.#############.
.#############.
.#############.
.#############.
.#############.
...............

#### Constraints

For this question, Python users are recommended to use PYPY over CPython.

#### Input Specification

The first line of input contains a single integer, .

The next lines describe the drawing. Each line consists of characters. Each character is either # or ..

It is guaranteed that all characters in the first and last rows of the drawing, as well as the first and last columns consist solely of #.

#### Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output a single integer, the total number of pumpkins in the drawing.

#### Sample Input 1

12
########################
#......................#
#.......#..............#
#.......#..............#
#.#############........#
#.#############........#
#.#############...#....#
#.#############.#####..#
#.#############.#####..#
#......................#
#......................#
########################

#### Sample Output 1

2

#### Sample Input 2

13
##########################
#........................#
#.........#.......#......#
#.......#####.....#......#
#.......#####...#####....#
#......#........#####....#
#....#####...............#
#....#####.....#.........#
#...........#######......#
#...........#.....#......#
#...........#######......#
#........................#
##########################

#### Sample Output 2

0