Wesley's Anger Contest 2 Problem 3 - Pumpkin Counting

View as PDF

Submit solution


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 N rows and 2N 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 M is a grid of pixels with 4 + \lfloor \frac{M}{5} \rfloor + \lceil \frac{2M}{3} \rceil rows and 2M + 5 columns, composed of only #, ., and characters. Here, can be thought of as a transparent pixel. A pumpkin of size M is considered to be in the drawing if there is a subgrid of the drawing with 4 + \lfloor \frac{M}{5} \rfloor + \lceil \frac{2M}{3} \rceil rows and 2M + 5 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 4 integers a, b, c, d. The rectangular region formed by all pixels that are in between rows a and b and columns c and d form the subgrid defined by a, b, c, d.

The 4 + \lfloor \frac{M}{5} \rfloor + \lceil \frac{2M}{3} \rceil rows of pixels of a pumpkin of size M are described below. Each row consists of 2M + 5 pixels.

  • The first row consists of (from left to right) M + 1 transparent pixels, 3 white pixels, and M + 1 transparent pixels.
  • The next \lfloor \frac{M}{5} \rfloor rows each consists of M + 1 transparent pixels, 1 white pixel, 1 black pixel, 1 white pixel, and M + 1 transparent pixels.
  • The next row consists of M + 2 white pixels, 1 black pixel, and M + 2 white pixels.
  • The next 1 + \lceil \frac{2M}{3} \rceil rows each consists of 1 white pixel, 2M + 3 black pixels, and 1 white pixel.
  • The last row consists of 2M + 5 white pixels.

Note that \lfloor x \rfloor is the largest integer less than or equal to x, and \lceil x \rceil is the smallest integer greater than or equal to x for a real number x.

Below is a pumpkin of size 5.

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

Constraints

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

3 \le N \le 1000

Input Specification

The first line of input contains a single integer, N.

The next N lines describe the drawing. Each line consists of 2N 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

Comments

There are no comments at the moment.