UniLecs #154. Тетрадь в клеточку - 2

Задача: у вас есть листочек тетради, он состоит из сетки клеточек N*N. Нектр клетки на листочке уже изрисованы.

Вам необходимо вырезать наибольший квадрат, ктр содержит "чистые" клетки. А также необходимо определить кол-во способов, ктр-м можно вырезать наибольший квадрат. Разрезать листочек можно только по границам клеток.

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

Arr - квадратная матрица N*N, состоящая из нулей и единиц (1 - означает, что клетка изрисована, 0 - чистая клетка). N - натуральное число от 1 до 1000.

Вывод: X - сторона наибольшего квадрата, ктр можно вырезать.

Count - кол-во способов, ктр-м можно вырезать наибольший квадрат.

Пример:

Листок бумаги размером 6*6. Черным помечены закрашенные клетки, белыми - чистые клетки. Как хорошо видно по рисунку, наибольший "незакрашенный" квадрат, ктр можно вырезать имеет размер 3*3. А кол-во способов, ктр-м это можно сделать, равно 2 (помечен синий и желтый квадрат).

Answer: X = 3; Count = 2.

Идея: воспользуемся методом динамического программирования. Пусть массив d[] хранит размер наибольшего квадрата, ктр можно вырезать из листочка (0,0) - (i, j) (клетка (i, j) принадлежит квадрату).

Рассмотрим след.случаи:

Если arr[i, j] == 1 (клетка изрисована), то d[i, j] = 0.

Если arr[i , j] == 0 ("чистая" клетка), то

1. arr[i - 1, j] = arr[i, j - 1] = k. Тогда d[i, j] зависит от значения в клетке arr[i - k, j - k]:
   - если arr[i - k, j - k] = 0, то весь квадрат (i - k, j - k) - (i, j) будет содержать только нули и d[i, j] = k + 1.
   - если arr[i - k, j - k] = 1, то d[i, j] = k.
   
2. arr[i - 1, j] != arr[i, j - 1]. Тогда d[i, j] = Min(d[i - 1, j], d[i, j - 1]) + 1.

Если обобщим два варианта, то получим след.формулу:

d[i, j] = Min(d[i - 1, j], d[i, j - 1], d[i - 1, j - 1]) + 1.

Реализация:

https://gist.github.com/unilecs/db6fdf9b450f53990f52997e1c7ab7d2

Test: https://dotnetfiddle.net/N17poc

Решения от подписчиков:

1. Антон, решение на Rust

https://gist.github.com/AnthonyMikh/d32380a2255409f201fd0a5b59dedb63

Test: https://play.rust-lang.org/?gist=14e84ca1c10fafb7262e672d1c23f429

2. Егор (@egormasharskii), решение на C++

Вычисляем максимальный квадрат с правым нижним углом в точке (i,j) на основе ужн вычесленного для точки (i-1,j-1) . Для этого нам также надо знать сколько свободных ячеек левее и выше точки (i,j)

https://gist.github.com/myegor/2927331724e50613bfbe95e8d176f8c3