## IOI '14 Practice Task 1 - Square

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

#### Cutting a square from a material

Jian-Jia has a piece of metal material and he wants to cut a square out of it. The material consists of by unit grids and Jian-Jia can only cut the material along grid boundary. Each grid is either usable or defective, and Jian-Jia wants to cut the largest possible square from the material without any defective grids. After determining the maximum size of the square, Jian-Jia also wants to know how many ways he can cut the largest square from this material. Finally Jian-Jia will report the product of the maximum size and the number of possible ways.

#### Example

Consider the by material in the following figure. The black grids are defective. The largest square Jian-Jia can cut from the material is by , and there are two ways to cut it – the red square and the green square. Jian-Jia will report the product of and , which is .

Your task is to find the size of largest squares in the material, count the number of ways to cut them, and report the product of the size and the number.

#### Input Specification

• Line 1: the size of the material ;
• Line :
• Each line has integers. A means the grid is useful and a means the grid is defective.

#### Output Specification

You must output one integer – the product of the size of largest square in the material, and the number of possible locations in the material.

#### Sample Input 1

6
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1

#### Sample Output 1

18

#### Sample Input 2

6
0 1 1 1 1 0
1 0 1 1 1 1
0 1 1 1 1 1
1 1 0 1 1 1
1 1 1 1 0 1
1 1 0 1 1 1

#### Sample Output 2

6