algorithm - 根据 2D Grid 中的点查找所有可能的矩形

Question

我得到了下面的 map

local Map = {
    [1] = {
        [1] = 'Sand',
        [2] = 'Sand',
        [3] = 'Sand'
    },
    [2] = {
        [1] = 'Sand',
        [2] = 'Sand',
        [3] = 'Grass'
    },
    [3] = {
        [1] = 'Rock',
        [2] = 'Rock',
        [3] = 'Grass'
    },
}

上图:

S = Sand
G = Grass
R = Rock

S S R
S S R
S G G

并尝试创建一个函数，我提供一个点，它返回一个包含该类型所有可能矩形的数组。

有点像

function GetRectangles(X, Y)
local Type = Map[X][Y]
local Result = {}
-- Get all rectangles with same type and add to array
return Result
end

因此，当我调用 GetRectangles(1, 1) 时，它会返回一个包含以下矩形的数组

• 从 1, 1 开始到 2, 2 结束的矩形
• 矩形开始于 1, 1 并结束于 1, 3

当我调用 GetRectangles(3, 3) 时，它会返回一个包含以下内容的数组

• 从 3, 3 开始到 2, 3 结束的矩形

我该怎么做？

Answer 1

考虑回溯。

recursive step:
    for each step in possible steps:
        check new rectangle for single type
            if ok, add to rectangle list and recurse

可能的步骤是:在左侧添加 1 列，在右侧添加 1 列，在上方添加 1 行，在下方添加 1 行。

例子:

current rectangle (1,1), (1,1)
   rectangle is ok
   add 1 row below:
   current rectangle (1,1), (1,2)
       rectangle is ok, add
       add 1 row below
            current rectangle (1,1) (1,3)
            rectangle ok, add
            // add 1 row below not possible step
            add 1 column left  
            rectangle (1,1) (2,3) not ok
            no more steps    
       add 1 column left
       rectangle (1,1) (2,1) not ok
       no more steps
   etc...

对于重叠，迭代列表并删除它们或提示:这可以在迭代期间完成。