В заданных массивах 1000 x 1000 существуют различные прямоугольники. в <Figure 1> последовательный "1", отображаемый как желтая ячейка, представляет собой узор прямоугольника. Минимальный размер прямоугольника в <Figure 1> равен 3 x 3, отображаемому как зеленая ячейка.
Внутри прямоугольника должно быть по крайней мере одно из "0".
Но в этом массиве также существует незакрытая форма или шаблон прямой линии.
(Начальное значение массива равно "0", а шаблоны представлены рядом "1". Они не перекрываются или не включаются друг в друга.)
Что может быть эффективным алгоритмом для поиска полных regtangles в массиве, кроме незакрытой формы или прямой линии? Например, на рисунке выше число полных прямоугольников равно 3
Ответ 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
Вот как выполняется алгоритм:
![enter image description here]()
1. Ошибка (и отмеченная) часть плохого прямоугольника
![enter image description here]()
2. Найден (и отмечен) прямоугольник.
![enter image description here]()
3. Не удалось выполнить одиночный квадрат (вертикальной линии)
![enter image description here]()
4. Ошибка на одном квадрате (вертикальной линии)
![enter image description here]()
5. Ошибка на одном квадрате (вертикальной линии)
![enter image description here]()
6. После многих подобных шагов найдите следующий прямоугольник.
![enter image description here]()
7. И следующий прямоугольник
![enter image description here]()
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----
