e-olymp
Задачи

Квадрат

Квадрат

У Джан-Джи имеется кусок металла, из которого он хочет вырезать квадрат. Кусок состоит из сетки n на n, которую Джан-Джи может разрезать только по границам сетки. Каждая ячейка сетки либо исправная либо дефектная, при этом Джан-Джи хочет вырезать наибольший квадрат, не содержащий дефектных клеток. После определения максимального размера квадрата Джан-Джи хочет узнать сколькими различными способами он может вырезать его из имеющегося куска. После чего Джан-Джи следует вывести произведение максимального размера на количество способов расположения наибольшего квадрата.

Рассмотрим кусок материала размера 6 на 6. Черные ячейки дефектные. Наибольший квадрат, который может вырезать Джан-Джи, имеет размер 3 на 3, причем имеется два варианта его вырезать - красный и зеленый квадраты. Джан-Джи выведет произведение 3 и 2, то есть 6.

prb7757.gif

Вам следует найти размер наибольшего квадрата, который можно вырезать из куска материала, а также посчитать, сколькими различными вариантами это можно сделать. После чего вывести их произведение.

Входные данные

Первая строка содержит размер материала n (1n1000). Каждая из следующих n строк содержит n целых чисел. 1 означает что участок сетки целый, а 0 означает что участок сетки поврежден.

Выходные данные

Вывести одно число – произведение размера наибольшего квадрата в материале на количество возможных его расположений в материале.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #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
Выходные данные #1
18
Входные данные #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
Выходные данные #2
6
Источник 2014 IOI, Practice Day 0