Алгоритм поиска пустых ячеек произвольного размера

[Kenix]

Всем привет. Я не сильно силен в матане, поэтому меня интересует вопрос. Как найти пустые ячейки произвольного размера ( + в произвольной таблице ) + в зависимости от позиции ячеек?

Если кто не понял, то вот примеры.

false - занятые ячейки, true - пустые

Пример 1. Нужно найти свободную ячейку 2 на 1 (высота, ширина)

  
local matrix = 
{ 
 { true, false, false }; 
 { true, false, true }; 
}; 
  
-- matrix[1][1]-->true 
-- matrix[2][1]-->true 
  

Пример 2. Нужно найти свободную ячейку 2 на 2 (высота, ширина)

  
local matrix = 
{ 
 { false, true, true }; 
 { true, true, true }; 
}; 
  
-- matrix[1][2]-->true 
-- matrix[1][3]-->true 
-- matrix[2][2]-->true 
-- matrix[2][3]-->true 
  

Пример 3. Нужно найти свободную ячейку 2 на 2 (высота, ширина)

  
local matrix = 
{ 
 { true, true, false }; 
 { false, true, true }; 
}; 
  
-- false 
  

[Elengar]

Страшный, ужасный, прожорливый и широколобый алгоритм, но зато я его сам написал .

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

function cellfind( arr, h, w ) 
    local len = #arr 
    h = h - 1 
    w = w - 1 
  
    for columPos, rowData in ipairs(arr ) do 
        for cellPos, cellData in ipairs(rowData) do 
            if cellData and not (columPos + h > len) and arr[columPos + h][cellPos + w] then 
                local free = true 
                for ii = columPos + 1, columPos + h do 
                    if not arr[ii][cellPos] or not free then  
                        free = false 
                        break 
                    end 
  
                    for jj = cellPos + 1, cellPos + w  do 
                        if not arr[ii][jj] then 
                            free = false 
                        end 
                    end 
                end 
                if free then print(string.format("[%d, %d] [%d, %d]", columPos, cellPos, columPos + h, cellPos + w)) end 
            end 
        end 
    end 
end 

[Kenix]

Спасибо огромное, это то что нужно!

[FranklinRoosevelt]

Страшный, ужасный, прожорливый и широколобый алгоритм, но зато я его сам написал .

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

function cellfind( arr, h, w ) 
    local len = #arr 
    h = h - 1 
    w = w - 1 
  
    for columPos, rowData in ipairs(arr ) do 
        for cellPos, cellData in ipairs(rowData) do 
            if cellData and not (columPos + h > len) and arr[columPos + h][cellPos + w] then 
                local free = true 
                for ii = columPos + 1, columPos + h do 
                    if not arr[ii][cellPos] or not free then  
                        free = false 
                        break 
                    end 
  
                    for jj = cellPos + 1, cellPos + w  do 
                        if not arr[ii][jj] then 
                            free = false 
                        end 
                    end 
                end 
                if free then print(string.format("[%d, %d] [%d, %d]", columPos, cellPos, columPos + h, cellPos + w)) end 
            end 
        end 
    end 
end 

Или у меня руки с ..., или здесь что-то не так:

local mat = 
{ 
 { true, false, false, false}, 
 { true, true, true, true}, 
 { true, true, true, true}, 
 { true, true, true, true} 
} 
  
h = 4 
w = 4 

в этом случае все равно возвращает true, и с другими размерами матриц так-же.

[Elengar]

Страшный, ужасный, прожорливый и широколобый алгоритм, но зато я его сам написал .

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

function cellfind( arr, h, w ) 
    local len = #arr 
    h = h - 1 
    w = w - 1 
  
    for columPos, rowData in ipairs(arr ) do 
        for cellPos, cellData in ipairs(rowData) do 
            if cellData and not (columPos + h > len) and arr[columPos + h][cellPos + w] then 
                local free = true 
                for ii = columPos + 1, columPos + h do 
                    if not arr[ii][cellPos] or not free then  
                        free = false 
                        break 
                    end 
  
                    for jj = cellPos + 1, cellPos + w  do 
                        if not arr[ii][jj] then 
                            free = false 
                        end 
                    end 
                end 
                if free then print(string.format("[%d, %d] [%d, %d]", columPos, cellPos, columPos + h, cellPos + w)) end 
            end 
        end 
    end 
end 

Или у меня руки с ..., или здесь что-то не так:

local mat = 
{ 
 { true, false, false, false}, 
 { true, true, true, true}, 
 { true, true, true, true}, 
 { true, true, true, true} 
} 
  
h = 4 
w = 4 

в этом случае все равно возвращает true, и с другими размерами матриц так-же.

Исправил.

- for i = columnPos + 1, columnPos + h do

+ for i = columnPos, columnPos + h do

function cellfind( arr, h, w ) 
    local len = #arr 
    h = h - 1 
    w = w - 1 
  
    for columnPos, rowData in ipairs(arr ) do 
        for cellPos, cellData in ipairs(rowData) do 
            if cellData and not (columnPos + h > len) and arr[columnPos + h][cellPos + w] then 
                local free = true 
                for i = columnPos, columnPos + h do 
                    if not arr[i][cellPos] or not free then 
                        free = false 
                        break 
                    end 
  
                    for j = cellPos + 1, cellPos + w  do 
                        if not arr[i][j] then 
                            free = false 
                        end 
                    end 
                end 
                if free then print(string.format("[%d, %d] [%d, %d]", columnPos, cellPos, columnPos + h, cellPos + w)) end 
            end 
        end 
    end 
end 

[FranklinRoosevelt]

Исправил.

- for i = columnPos + 1, columnPos + h do

+ for i = columnPos, columnPos + h do

function cellfind( arr, h, w ) 
    local len = #arr 
    h = h - 1 
    w = w - 1 
  
    for columnPos, rowData in ipairs(arr ) do 
        for cellPos, cellData in ipairs(rowData) do 
            if cellData and not (columnPos + h > len) and arr[columnPos + h][cellPos + w] then 
                local free = true 
                for i = columnPos, columnPos + h do 
                    if not arr[i][cellPos] or not free then 
                        free = false 
                        break 
                    end 
  
                    for j = cellPos + 1, cellPos + w  do 
                        if not arr[i][j] then 
                            free = false 
                        end 
                    end 
                end 
                if free then print(string.format("[%d, %d] [%d, %d]", columnPos, cellPos, columnPos + h, cellPos + w)) end 
            end 
        end 
    end 
end 

Спасибо, очень полезная штука, а то я циклом переберал матрицу.

[Kenix]

Кому нужна функция на эту же тему, забирайте.

  
-- aInputTable - заполненная таблица 
-- iMaxRows, iMaxColumns - максимальное число строк/столбцов 
-- iX, iY - позиция ячейки 
-- iW, iH - ширина и высота ячейки 
-- bState - заполнена/не заполнена 
  
function FillCells( aInputTable, iMaxRows, iMaxColumns, iX, iY, iW, iH, bState ) 
    for iRow = 1, iMaxRows do 
        for iColumn = 1, iMaxColumns do 
            if ( iRow >= iY and iRow < iY + iH ) and ( iColumn >= iX and iColumn < iX + iW ) then 
                aInputTable[ iRow ][ iColumn ] = bState; 
            end 
        end 
    end 
end