Jump to content

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


Kenix

Recommended Posts

  • Other Languages Moderators

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

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

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 
  

Link to comment

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

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

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 

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

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

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, и с другими размерами матриц так-же.

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

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

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 

Link to comment

Исправил.

- 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 

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

Link to comment
  • 3 weeks later...
  • Other Languages Moderators

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

  
-- 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 
  

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...