在二维格点中,找出所有基于点的可能矩形。

我得到了以下地图

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的矩形

我该如何做到这一点?

点赞
用户1503710
用户1503710

考虑回溯法。

递归步骤:
    对于可能的步骤中的每一个步骤:
        检查新矩形是否为单一类型
            如果是,将其添加到矩形列表中并递归

其中可能的步骤是:向左添加一列,向右添加一列,向上添加一行,向下添加一行。

例如:

当前矩形(1,1),(1,1)
   矩形是合法的
   向下添加1行:
   当前矩形(1,1),(1,2)
       矩形是合法的,添加
       向下添加1行
            当前矩形(1,1)(1,3)
            矩形是合法的,添加
            //向下添加1行不是可能的步骤
            向左添加1列
            矩形(1,1)(2,3)不是合法的
            没有更多的步骤
       向左添加1列
       矩形(1,1)(2,1)不是合法的
       没有更多的步骤
   等等 ...

对于重叠部分,可以迭代列表并删除它们或提示:可以在迭代过程中完成。

2013-11-17 16:12:47