Максимальный белый прямоугольник

Question

Максимальный белый прямоугольник

Рейтинг: 12Ответов: 1Опубликовано: 29.01.2011

Один из моих знакомых, дает очень интересные задачи на собеседованиях. Некоторые из которых, мне очень интересно решать. Вот одна из таких.

Дано прямоугольное поле из черных и белых клеток в произвольном порядке. Белым прямоугольником называется прямоугольная область, которая содержит только белые клетки. Максимальным белым прямоугольником называется любой белый прямоугольник максимальной площади.

Предложите алгоритм, который находит максимальный белый прямоугольник.
Сколько времени он работает? Можно ли быстрее?
Приведите оценку снизу для сложности алгоритма.

В рамках форума, предлагаю обсудить алгоритм решения задачи. На вход имеем двумерный массив типа char. Белая позиция - это пробел, черная - любой другой символ.

c# алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 3

Придумалось вот такое вот решение:

#include <iostream>
#include <algorithm>

// Включает левую верхнюю точку, исключает правую нижнюю
struct Rect
{
    Rect() :
        x1(0), y1(0), x2(0), y2(0)
    {}
    Rect(int x1, int y1, int x2, int y2) :
        x1(x1), y1(y1), x2(x2), y2(y2)
    {}
    int x1, y1, x2, y2;
};

Rect solve(const char** field, int width, int height)
{
    struct Local_
    {
        Rect answerRect;
        int answer;
        int y;
        int* up;

        void tryRect(int l, int r)
        {
            int minv = *std::min_element(up + l, up + r);
            if (minv * (r - l) > answer)
            {
                answer = minv * (r - l);
                answerRect = Rect(l, y - minv + 1, r, y + 1);
            }
            for (int i = 0, k = -1; 2 * i - (k + 1) / 2 < r - l;
                 i += (1 - k) / 2, k *= -1) // порядок ...6420135...
            {
                int x = (r - l) / 2 + k * i;
                if (up[x] == minv)
                {
                    if (x > l)
                        tryRect(l, x);
                    if (x + 1 < r)
                        tryRect(x + 1, r);
                    break;
                }
            }
        };
    } local;

    local.answer = 0;
    local.up = new int[width];
    std::fill_n(local.up, width, 0);
    int& y = local.y;
    for (y = 0; y < height; ++y)
    {
        for (int x = 0; x < width; ++x)
        {
            if (field[x][y] == ' ')
                ++local.up[x];
            else
                local.up[x] = 0;
        }
        local.tryRect(0, width);
    }
    delete [] local.up;
    return local.answerRect;
}

Время работы на поле h*w в худщем случае O(h^2 * w), хотя на случайном вводе будет работать очень быстро: O(h * log(h) * w). В качестве улучшения можно транспонировать ввод, если h > w, что позволяет добиться O(min(h, w)^2 * max(h, w)). Зато используется только O(w + h) дополнительной памяти :)

Если говорить об оценке снизу, то я сомневаюсь в существовании решения за O(h * w), потому что для каждой клетки приходится перебирать omega(1) прямоугольников-кандидатов и выбирать среди них максимум по площади. Возможно, кандидатов даже Theta(min(h, w)), хотя доказать эту оценку я не могу.

Максимальный белый прямоугольник

Ответы