7757. Квадрат
У Джан-Джи
имеется металлическая заготовка, из которой он хочет вырезать квадрат.
Заготовка представляет собой квадратную сетку размера n × n, при этом
разрезы можно выполнять только по линиям сетки.
Каждая ячейка
сетки либо исправна, либо дефектна. Джан-Джи хочет вырезать квадрат
максимального размера, не содержащий ни одной дефектной ячейки. После
определения максимального возможного размера квадрата ему необходимо
определить, сколькими различными способами можно вырезать такой квадрат из
заготовки.
Итогом является
произведение размера наибольшего квадрата на количество способов его
размещения.
Рассмотрим
пример заготовки размера 6 × 6. Чёрные ячейки являются дефектными.
Наибольший квадрат, который можно вырезать, имеет размер 3 × 3. При этом
существует два различных способа его размещения (обозначены красным и зелёным
цветами). Следовательно, Джан-Джи выведет произведение 3 * 2 = 6.
Вам следует найти
максимальный размер квадрата, который можно вырезать из заданной заготовки, а
также количество различных способов его размещения. В качестве ответа выведите
произведение этих величин.
Вход. Первая строка содержит одно целое число n (1 ≤ n
≤ 1000) – размер заготовки.
Каждая из следующих n
строк содержит по n целых чисел. Число 1 означает, что
соответствующая ячейка исправна, а число 0 – что она дефектна.
Выход. Выведите одно целое число – произведение размера
наибольшего квадрата без дефектных ячеек на количество возможных его
размещений.
|
Пример
входа 1 |
Пример
выхода 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 |
18 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 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 |
6 |
РЕШЕНИЕ
динамическое
программирование
Анализ алгоритма
Введём двумерный массив dp, где:
·
dp[i][j] – сторона наибольшего квадрата,
состоящего только из единиц, с правым нижним углом в клетке (i, j).
Пусть массив m задаёт исходную сетку.
Базовые случаи
·
Если m[i][j] = 0 (клетка дефектная), то
никакой квадрат в клетке (i, j) заканчиваться не может. Поэтому
dp[i][j] = 0;
·
Если клетка находится на границе (i = 0 или j
= 0) и m[i][j] = 1, то возможен только квадрат размера 1. Поэтому
dp[i][j] = 1
Переходы динамики
Пусть m[i][j]
= 1. Рассмотрим два случая:
1.
Предположим, что m[i – 1][j] = m[i][j
– 1] = k. Тогда значение dp[i][j]
зависит от состояния
ячейки
m[i – k][j – k]:
·
если m[i – k][j
– k] = 1, то весь квадрат с углами (i – k,
j – k) и (i, j) состоит только из единиц, поэтому dp[i][j]
= k + 1.
·
если m[i – k][j
– k] = 0, то увеличить квадрат нельзя, и dp[i][j]
= k.
2.
Если m[i – 1][j] ≠ m[i][j – 1], то значение dp[i][j]
определяется
как
dp[i][j]
= min(dp[i – 1][j], dp[i][j – 1]) + 1
Обобщая выше сказанное,
получаем формулу:
dp[i][j]
= min(dp[i – 1][j], dp[i][j – 1], dp[i – 1][j – 1]) + 1
Рассмотрим второй тест. Заполним для него массив dp.
Имеются два наибольших квадрата размером 3 * 3. Произведение
размера наибольшего квадрата на количество его расположений равно 3 * 2 = 6.
Реализация алгоритма
Объявим рабочий массив dp.
#define MAX 1010
int dp[MAX][MAX];
Читаем значение n. Переменная size хранит размер наибольшего квадрата, cnt – количество таких квадратов в заданной сетке. Массив dp предварительно
инициализируем нулями.
scanf("%d", &n);
memset(dp,0,sizeof(dp));
size = cnt = 0;
Перебираем элементы массива dp построчно: строки – в порядке возрастания, а внутри
каждой строки – столбцы также по возрастанию.
for(i = 1; i
<= n; i++)
for(j = 1; j
<= n; j++)
{
scanf("%d",&val);
Предположим, что все значения массива dp до клетки (i, j) уже вычислены. Читаем очередное значение val = m[i][j]. При этом входную матрицу целиком в
памяти не храним – обрабатываем её на лету.
Так как массив dp изначально инициализирован нулями, при val
= 0 значение dp[i][j] автоматически остаётся равным нулю.
if (val ==
1)
{
dp[i][j] =
min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]) + 1;
Пересчитываем значения size и cnt для текущего квадрата
размером dp[i][j].
if
(dp[i][j] == size) cnt++;
if
(dp[i][j] > size) {size = dp[i][j]; cnt = 1;}
}
}
Выводим ответ.
printf("%lld\n",1LL * size * cnt);