1643 - Searching for Stars

Created by Yonny Mondelo Hernández
Added by ymondelo20 (2011-11-29)
Limits
Total Time: 50000 MS | Test Time: 10000 MS |Memory: 62 MB | Output: 64 MB | Size: 29 KB
Enabled languages
Available in

Description

A young programmer Vasha can't get this question out of his head! How many stars are there in the sky? He took a photo of the sky using his digital camera and now he analyzes the resulting monochrome digital picture. The picture is represented by a rectangular matrix consisting of N lines each containing M characters. A character equals '1', if the corresponding photo pixel is white and '0', if it is black.

Vasha thinks that he has found a star on the photo if he finds a white pixel surrounded by four side-neighboring pixels that are also white:
  1
111
  1
a star on the photo.

Vasha wish to cut out a rectangular area from the photo which contain no less than K stars. The stars can intersect, have shared white pixels on the photo. Vasha will cut out the rectangular area so that its borders will be parallel to the sides of the photo and the cuts will go straight between the pixel borders.

So easy, it said. But Vasha keeps wondering how many ways there are to cut an area out of the photo so that it met the conditions given above. Can you help Vasha for finding this number.
A young programmer Vasha can't get this question out of his head! How many stars are there in the sky? He took a photo of the sky using his digital camera and now he analyzes the resulting monochrome digital picture. The picture is represented by a rectangular matrix consisting of N lines each containing M characters. A character equals '1', if the corresponding photo pixel is white and '0', if it is black.

Vasha thinks that he has found a star on the photo if he finds a white pixel surrounded by four side-neighboring pixels that are also white:
  1
111
  1
a star on the photo.

Vasha wish to cut out a rectangular area from the photo which contain no less than K stars. The stars can intersect, have shared white pixels on the photo. Vasha will cut out the rectangular area so that its borders will be parallel to the sides of the photo and the cuts will go straight between the pixel borders.

So easy, it said. But Vasha keeps wondering how many ways there are to cut an area out of the photo so that it met the conditions given above. Can you help Vasha for finding this number.
A young programmer Vasha can't get this question out of his head! How many stars are there in the sky? He took a photo of the sky using his digital camera and now he analyzes the resulting monochrome digital picture. The picture is represented by a rectangular matrix consisting of N lines each containing M characters. A character equals '1', if the corresponding photo pixel is white and '0', if it is black.

Vasha thinks that he has found a star on the photo if he finds a white pixel surrounded by four side-neighboring pixels that are also white:
  1
111
  1
a star on the photo.

Vasha wish to cut out a rectangular area from the photo which contain no less than K stars. The stars can intersect, have shared white pixels on the photo. Vasha will cut out the rectangular area so that its borders will be parallel to the sides of the photo and the cuts will go straight between the pixel borders.

So easy, it said. But Vasha keeps wondering how many ways there are to cut an area out of the photo so that it met the conditions given above. Can you help Vasha for finding this number.

Input specification

The first line of the input contains three integers N, M, and K (1 <= N,M <= 500; 1 <= K <= N*M). Then follow N lines, containing the description of the given photo as a sequence of lines. Each line contains M characters '0' or '1'.
The first line of the input contains three integers N, M, and K (1 <= N,M <= 500; 1 <= K <= N*M). Then follow N lines, containing the description of the given photo as a sequence of lines. Each line contains M characters '0' or '1'.
The first line of the input contains three integers N, M, and K (1 <= N,M <= 500; 1 <= K <= N*M). Then follow N lines, containing the description of the given photo as a sequence of lines. Each line contains M characters '0' or '1'.

Output specification

The number of ways for cut an area out of the given photo, so that it met the conditions given above.
The number of ways for cut an area out of the given photo, so that it met the conditions given above.
The first line of the input contains three integers N, M, and K (1 <= N,M <= 500; 1 <= K <= N*M). Then follow N lines, containing the description of the given photo as a sequence of lines. Each line contains M characters '0' or '1'.

Sample input

5 5 4
11111
11111
11111
11111
11111

Sample output

9

Hint(s)

We'll number the rows and columns below starting from 1, the coordinates (r, c) will denote a cell in row r, column c. Then, in the sample any rectangle whose each side is no less than four, will do. The possible rectangle sizes are 4 × 4, 4 × 5, 5 × 4 and 5 × 5. Such figures can be cut in 4 ways, 2 ways, 2 ways and 1 way correspondingly.
We'll number the rows and columns below starting from 1, the coordinates (r, c) will denote a cell in row r, column c. Then, in the sample any rectangle whose each side is no less than four, will do. The possible rectangle sizes are 4 × 4, 4 × 5, 5 × 4 and 5 × 5. Such figures can be cut in 4 ways, 2 ways, 2 ways and 1 way correspondingly.
We'll number the rows and columns below starting from 1, the coordinates (r, c) will denote a cell in row r, column c. Then, in the sample any rectangle whose each side is no less than four, will do. The possible rectangle sizes are 4 × 4, 4 × 5, 5 × 4 and 5 × 5. Such figures can be cut in 4 ways, 2 ways, 2 ways and 1 way correspondingly.