Поиск полных прямоугольников, содержащих 0

Ответ 1

Это довольно просто. Если у вас есть квадраты n, вы можете подсчитать прямоугольники в O(n).

Предположения:

• Границы каждого правильного прямоугольника не разделяют какие-либо ячейки с недействительным путем.
• Если один прямоугольник внутри другого, вы были бы счастливы найти их

Вам понадобится дополнительная память размером с входной. Позвольте называть это visited и инициализировать с помощью 0.

Сначала построим вспомогательную функцию:

is_rectangle(square s)
    from s, go right while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go down while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go left while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go up while you see 1s and visited is 0
        mark them as 1 in visited
    if then one above is not s
        return 0
    return 1

Эта функция в основном отслеживает 1s в направлениях справа налево-вверх и проверяет, соблюдены ли условия (длина не менее 3 и достижение начальной позиции). Он также отмечает посещенные квадраты.

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

Теперь решение проблемы легко:

num_rectangles = 0
initialize visited to 0 (rows x columns)
for r in rows
    for c in columns
        if visitied[r][c] or image[r][c] == 0
            continue
        num_rectangles += is_rectangle(<r,c>)
return num_rectangles

Вот как выполняется алгоритм:

1. Ошибка (и отмеченная) часть плохого прямоугольника

2. Найден (и отмечен) прямоугольник.

3. Не удалось выполнить одиночный квадрат (вертикальной линии)

4. Ошибка на одном квадрате (вертикальной линии)

5. Ошибка на одном квадрате (вертикальной линии)

6. После многих подобных шагов найдите следующий прямоугольник.

7. И следующий прямоугольник

8. Окончание алгоритма

Ответ 2

Следующий алгоритм O (n) будет работать на любой 2D-матрице значений 0/1 (т.е. допускаются пересекающиеся/перекрывающиеся прямоугольники, а также произвольные непрямоугольные открытые/закрытые фигуры), Определение прямоугольника, которое я использую здесь, это "внутренность целиком состоит из 0-клеток" (так, например, если один прямоугольник целиком содержит другой, будет найден только внутренний прямоугольник, если также следует рассмотреть прямоугольники, каждый найденный прямоугольник может быть удален и алгоритм перезапущен). Это основано на наблюдении, что каждая 0-ячейка может находиться внутри не более одного 1-прямоугольника.

Я использую соглашение о том, что x = 0 - крайняя левая позиция, а y = 0 - верхнее положение.

• Найдите верхний левый угол.. Начиная с верхней левой ячейки и продолжая влево-вправо и сверху вниз, найдите следующую невидимую ячейку, которая может быть левым верхним угол прямоугольника сплошного прямоугольника: в частности, он должен быть 0-ячейкой, которая имеет 1-клеточные соседи в положениях SW, W, NW, N и NE и 0-ячейки в остальных 3 соседних положениях.
• Найдите верхний правый угол.. Сканируйте соседей справа, пока эти ячейки равны 0 и имеют соседний N-ячеек.
• Может ли это быть верхней строкой сплошного 0-прямоугольника? Если последняя ячейка, найденная вышеприведенным циклом до ее окончания, является ячейкой, которая может быть верхней правой ячейкой в ​​твердом теле -0 (в частности, 0-ячейка, имеющая 1-клеточные соседи в ячейках NW, N, NE, E и SE и 0-клетки в остальных 3-х позициях), то мы установили как верхнюю координату y, так и точную ширину единственно возможного сплошного 0-прямоугольника, который использует любую из этих ячеек. Если последняя ячейка не соответствует этим условиям верхнего правого угла, то ни одна из этих ячеек не может быть частью сплошного 0-прямоугольника: отметьте их посещенными и goto 1.
• Вызвать начальную и конечную х координаты полосы 0-ячеек x1 и x2; вызовите вертикальное положение y1.
• Сканирование вниз, строка в момент времени. Установите y2 = y1, а в то время как линия между x1 и x2 в вертикальном положении y2 может быть частью сплошного 0-прямоугольника, приращение y2. В частности, тест в каждом вертикальном положении y2 равен: ячейки в (x1 - 1, y2) и (x2 + 1, y2) должны быть равны 1, а все ячейки между ними должны быть 0.
• Может ли это быть нижней строкой сплошного 0-прямоугольника? Если последняя строка, найденная предыдущим циклом до ее окончания, является строкой, которая может быть нижней строкой сплошного 0-прямоугольника (в частности, есть 1-клетки от пути (x1 - 1, y2 + 1) до (x2 + 1, y2 + 1)), то мы нашли полный сплошной 0-прямоугольник, окруженный 1-клетками: если его размер больше, чем самый большой, обнаруженный до сих пор, а затем записывать его как новый самый большой прямоугольник. В противном случае (если в следующей строке нет сплошной строки 1-ячеек), ни один из рассмотренных 0-клеток не может быть частью какого-либо сплошного 0-прямоугольника: пометить их как посетив и перейти 1.

Ответ 3

Если вы можете иметь только прямоугольные формы в своем массиве, это эквивалентно классической проблеме вычисления на двоичных изображениях: просто примените стандартный алгоритм для подключенных компонентов. Вы помечаете только подключенные компоненты 0 и считаете их.

См. http://en.wikipedia.org/wiki/Connected-component_labeling, например. Этот тип алгоритма довольно прост на изображениях, но требует некоторого объема памяти (такого же размера, как ваш входной массив, типа short или int). Будьте осторожны с подключением: если вы выберете 4-соединение, вы будете считать замкнутые прямоугольники, даже если некоторые углы отсутствуют. Но алгоритм проще, чем с 8-связностью.

Если у вас могут быть более сложные замкнутые фигуры, просто добавьте пост-обработку: для каждого подключенного компонента подсчитайте количество пикселей внутри ограничивающего прямоугольника компонента (если оба числа равны, у вас есть прямоугольник)

Ответ 4

Думал об этом некоторое время. Я придумал этот метод:

1) устранить все нули вокруг ребер - изменить их значение на 2

2) заливка заполняет матрицу вокруг 2s

это оставляет вам только остров нулей, который теперь можно проверить на выпуклость. Итак, для каждого острова:

3) найдите степень 0 в X и Y - дайте вам потенциальный внутренний прямоугольник

4), если внутренний прямоугольник содержит 1 ИЛИ внешний прямоугольник содержит 0, заливка заливает этот остров 2s, поскольку он не выпуклый (следовательно, не прямоугольник)

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

И теперь для кода (извините C sharp):

using System;
using System.Collections.Generic;

namespace Test
{
class MainClass
{
    static private int [,] matrix = new int[,] {
        {0,0,0,0,0,0,0,0,1,1,1,1,0,0,0},
        {0,1,1,1,1,1,1,0,1,0,0,1,0,1,0},
        {0,1,0,0,0,0,1,0,1,0,0,1,0,1,0},
        {0,1,0,0,0,0,1,0,1,0,0,1,0,1,0},
        {0,1,0,0,0,0,1,0,1,0,0,0,0,1,0},
        {0,1,0,0,0,0,1,0,1,0,0,0,0,1,0},
        {0,1,1,1,1,1,1,0,1,0,0,1,0,1,0},
        {0,0,0,0,0,0,0,0,1,1,1,1,0,0,0},
        {0,0,1,1,1,1,0,0,0,0,0,0,0,0,0},
        {0,0,1,0,0,1,0,0,1,1,1,0,1,1,0},
        {0,0,1,1,1,1,0,0,1,0,1,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,1,1,0,0,0,0}
    };

    static private int width = matrix.GetLength(0);
    static private int height = matrix.GetLength(1);

    private const int DEAD = 2;
    private const int RECT = 3;

    public static void Main (string[] args)
    {
        //width = matrix.GetLength(0);
        //height = matrix.GetLength(1);

        PrintMatrix ();
        EliminateFromEdges (DEAD);
        PrintMatrix ();
        FloodFill (DEAD); // very inefficient - find a better floodfill algorithm
        PrintMatrix ();

        // test each island of zeros for convexness
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                if (matrix[i,j] == 0)
                {
                    if (TestIsland(i,j) == false)
                    {
                        // eliminate this island as it is not convex
                        matrix[i,j] = DEAD;
                        FloodFill(DEAD);
                        PrintMatrix ();
                    }
                    else
                    {
                        // flag this rectangle as such
                        matrix[i,j] = RECT;
                        FloodFill(RECT);
                        PrintMatrix ();
                    }
                }
            }
        }

        // We're done, anything flagged as RECT can be expanded to yield the rectangles
        PrintMatrix ();
    }

    // flag any zero at edge of matrix as 'dead'
    static private void EliminateFromEdges(int value)
    {
        for (int i = 0; i < width; i++) 
        {
            if (matrix [i, 0] == 0) 
            {
                matrix [i, 0] = value;
            }
            if (matrix [i, height - 1] == 0)
            {
                matrix [i, height - 1] = value;
            }
        }
        for (int j = 1; j < height - 1; j++)
        {
            if (matrix [0, j] == 0)
            {
                matrix [0, j] = value;
            }
            if (matrix [width - 1, j] == 0)
            {
                matrix [width - 1, j] = value;
            }
        }
    }

    // propagte a value to neighbouring cells
    static private void FloodFill (int value)
    {
        bool change_made = true; // set to true to start things off
        while (change_made) {
            change_made = false;
            for (int i = 1; i < width - 1; i++) {
                for (int j = 1; j < height - 1; j++) {
                    if ((matrix [i, j] == 0) &&
                        ((matrix [i - 1, j] == value) || 
                        (matrix [i + 1, j] == value) ||
                        (matrix [i, j - 1] == value) || 
                        (matrix [i, j + 1] == value))) {
                        matrix [i, j] = value;
                        change_made = true;
                    }
                }
            }
        }
    }

    static private bool TestIsland (int x, int y)
    {
        // find convex extend of island
        int x2 = x;
        int y2 = y;
        while (matrix[++x2, y] == 0);
        x2--;
        while (matrix[x,++y2] == 0);
        y2--;

        // check inner cells (want all zeroes)
        for (int i = x; i <= x2; i++) 
        {
            for (int j = y; j <= y2; j++) 
            {
                if (matrix[i,y] != 0)
                {
                    return false;
                }
            }
        }

        // check surrounding cells (want all ones)
        x--; y--;
        x2++; y2++;
        for (int i = x; i <= x2; i++) 
        {
            if ((matrix[i,y] != 1) || (matrix[i,y2] != 1))
            {
                return false;
            }
        }
        for (int j = y + 1; j <= y2 - 1; j++) 
        {
            if ((matrix[x,j] != 1) || (matrix[x2,j] != 1))
            {
                return false;
            }
        }

        return true;
    }

    // for debug purposes
    static private void PrintMatrix ()
    {
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                switch(matrix[i,j])
                {
                case DEAD:
                    Console.Write("-");
                    break;
                case RECT:
                    Console.Write("+");
                    break;
                default:
                    Console.Write(matrix[i,j]);
                    break;
                }
            }
            Console.WriteLine();
        }
        Console.WriteLine();
    }
}
}

Вывод этого кода

000000001111000
011111101001010
010000101001010
010000101001010
010000101000010
010000101000010
011111101001010
000000001111000
001111000000000
001001001110110
001111001010000
000000001110000

--------1111---
-1111110100101-
-1000010100101-
-1000010100101-
-1000010100001-
-1000010100001-
-1111110100101-
-0000000111100-
-0111100000000-
-0100100111011-
-0111100101000-
--------111----

--------1111---
-111111-1--1-1-
-100001-1--1-1-
-100001-1--1-1-
-100001-1----1-
-100001-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1001--111-11-
--1111--101----
--------111----

--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1001--111-11-
--1111--101----
--------111----

--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--101----
--------111----

--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--1+1----
--------111----

--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--1+1----
--------111----

Ответ 5

Это то, что я думаю, может быть довольно неэффективным. Не знаю об этом.

• Пройдите по строке, если вы не найдете как минимум 3 1 s.
• Поверните вниз и выполните boolean и выполните операции со строками ниже → они должны привести к формату 100..001, если это допустимый прямоугольник. (Предполагая, что вы можете выполнять все операции boolean)
• Вы нашли прямоугольник, когда на шаге 2 вы нашли хотя бы одну строку и, наконец, все 1 s.
• Повторите со следующим элементом строки!