Белый Прямоугольник (классическая задачка вместо приветствия)

Оказывается Хабр доброжелательно предоставляет возможность завести бесплатный «корпоративный» блог для опенсорсного проекта. Какое-то время назад я подал заявку — и недавно обнаружил что она была удовлетворена. Начинать программисты любят с «тестового» поста, но т.к. речь идёт о публичном пространстве, пусть он будет хоть немного содержательным 🙂

На сайт CodeAbbey сегодня добавилась задачка про поиск Белого Прямоугольника. Речь идёт о матрице в которой есть чёрные и белые клетки — расставленные достаточно хаотично — и хочется найти прямоугольник без чёрных клеток максимальной площади (со сторонами параллельными сторонам матрицы, конечно).

Про сам сайт мы ещё расскажем в отдельно (иначе зачем блог было заводить) — а сейчас всё же про саму задачку.

Она, по-видимому, древняя как мир. Я на неё наткнулся где-то в конце книжки Ж.Арсака «Программирование Игр и Головоломок» — причём он упоминает что сам встретил её на какой-то олимпиадке за несколько лет до того. А книжка-то 1985 года.

Интересно что при очень простом описании самый банальный алгоритм который приходит в голову имеет сложность O(N^6) где N — сторона матрицы. Конечно нынешние компьютеры уже не те что в 80х годах, но если вы заимплементите такой «брутефорс» — то даже на скромных размерах тестовых данных которые предлагает сайт, работать он у вас будет сколько-то секунд… Заметно не мгновенно.

Гораздо более сносный алгоритм O(N^3) можно реализовать достаточно несложно (именно он срабатывает при загрузке страницы и генерации данных на сайте).

Возможно оптимальный алгоритм за O(N^2) уже требует немножко поднапрячь мозги — но впрочем его не очень сложно нагуглить (сложнее понять).