2
4

3 回答 3

0

当然。

要找到一个矩形：

  • 从任何空闲单元格开始。假设这将是左上角。
  • 看看能不能横向展开。
  • 看看是否可以垂直扩展。
  • 回溯。

稍后我将对此进行详细说明，但我认为这可以让您快速开始。

于 2013-08-29T16:47:25.183 回答
0

我之前的回答是简单的方法。这是一个完全不同的。

算法

  1. 识别水平运行并转换为矩形表示法。

  2. currRects用第 0 行中的矩形初始化列表。

  3. 将 currRow 设置为 1。

  4. 对于 中的每个矩形，b在row中currRects找到与水平线的交点。相交操作定义为acurrRowi

        r(axi-axt,ayi-ayt) i r(bxi-bxt,byi-byt)

    它的相关性是两个矩形的y范围如何相交。用图形描绘它：

           bbb
    aa|   |     No intersect
    aa|aa |     Partial intersect
    aa|aaa|     a contains b
    aa|aaa|a    a contains b
      |aa |     b contains a
      |aaa|     a equal b
      |aaa|a    a contains b
      | aa|     b contains a
      | aa|a    Partial intersect
      |   |aa   No intersect

    确定每种情况的必要逻辑基于ayi、ayt、byi、byt和 简单，因此这里不再描述。

    此函数将返回最多 2 个矩形和一个标志的列表。

        No intersect       ([],true)
    Partial intersect: ([red,a],true)
    b contains a:      ([red],true)
    a contains b:      ([pres,a],false)
    a equal b:         ([pres],false)

    red并且pres是将前一个矩形b与传入的a. 它可以pres遍历矩形的宽度（在 y 坐标的意义上），或者red使用它，但算法上的区别并不重要。

    第 4 步的核心是保留一个nextCurrRects包含 function 返回的所有矩形的列表intersect。 nextCurrRects当然，最初应该是空的。b此外，如果对于前面的矩形，currRects返回的标志是 never false，则b需要将其放入最终结果列表中（或者只是打印或“生成”）。

  5. 使currRects等于nextCurrRects。currRow如果还没有到达终点，则进行迭代。

  6. 仍然存在的所有矩形currRects也属于结果。

例子

1)inRects= [ r(0-0,2-2), r(1-1,0-2), r(2-2,0-1) ]

2)currRects= [ r(0-0,2-2) ]

3)currRow= 1

4) 

    nextCurrRects= []
    r(1-1,0-2) i r(0-0,2-2) {a contains b} == ( [ r(0-1,2-2), r(1-1,0-2)] ], false )
    nextCurrRects == [ r(0-1,2-2), r(1-1,0-2)] ]

5)currRects == [ r(0-1,2-2), r(1-1,0-2)] ]

4) 

    nextCurrRects= []

    r(2-2,0-1) i r(0-1,2-2) {No intersect} == ( [], true )
    Never false -> result= [ r(0-1,2-2) ]

    r(2-2,0-1) i r(1-1,0-2) {Partial intersect} == ( r(1-2,0-1), true )
    nextCurrRects= [ r(1-2,0-1) ]
    Never false -> result= [ r(0-1,2-2) , r(1-2,0-1) ]

5)currRects= [ r(1-2,0-1) ]

6)result= [ r(0-1,2-2) , r(1-2,0-1) , r(1-2,0-1) ]

事实上，该算法刚刚“发现”在原始示例中没有考虑第三个结果矩形：

    [x][x][3]
    [ ][ ][3]
    [ ][ ][x]

代码

class Range:
    def __init__(self,start,end=None):
        self.start= start
        self.end= end if end is not None else start
    def isEmpty(self):
        return self.start > self.end
    def isUnit(self):
        return self.start == self.end
    def intersect(self,other):
        return Range( max(self.start,other.start) , min(self.end,other.end) )
    def contains(self,other):
        return self.start <= other.start and self.end >= other.end 
    def __repr__(self):
        return "Range(%d,%d)" % ( self.start, self.end )

class Rect:
    def __init__(self,xRange,yRange):
        self.xRange= xRange
        self.yRange= yRange
    def isEmpty(self):
        return self.xRange.isEmpty() or self.yRange.isEmpty()
    def isUnit(self):
        return self.xRange.isUnit() and self.yRange.isUnit()
    def intersect(self,other):
        return Range( max(self.start,other.start) , min(self.end,other.end) )
    def contains(self,other):
        return self.xRange.contains(other.xRange) and self.yRange.contains(other.yRange)
    def __repr__(self):
        return "Rect(%s,%s)" % ( self.xRange, self.yRange )

def intersect(a,b):
    r= Rect( Range(b.xRange.start,a.xRange.end) , a.yRange.intersect(b.yRange) )
    brokenB= not a.yRange.contains(b.yRange)
    fullyAbsorbedA= b.yRange.contains(a.yRange)
    return (r,brokenB,fullyAbsorbedA)

def findOpenRectangles(freeElements,pastRowNum):        

    #  From `freeElements`, compute free runs into `freeRunsPerRow`
    from collections import defaultdict
    freeRunsPerRow= defaultdict(set)
    rowNum= -1
    currRun= None
    for fe in freeElements :
        if fe[0] != rowNum :
            if currRun is not None:
                freeRunsPerRow[rowNum]|= { Rect(Range(rowNum),currRun) }
            currRun= Range(fe[1],fe[1])
            rowNum= fe[0]
        elif fe[1] == currRun.end + 1 :
            currRun= Range(currRun.start,fe[1])
        else:
            freeRunsPerRow[rowNum]|= { Rect(Range(rowNum),currRun) }
            currRun= Range(fe[1],fe[1])
    if currRun is not None:
        freeRunsPerRow[rowNum]|= { Rect(Range(rowNum),currRun) }
        currRun= None
    for freeRuns in freeRunsPerRow.items() :
        print( freeRuns )

    #  Yield open rectangles
    currRects= set()
    for currRow in range(0,pastRowNum) :
        continuingRects= set()
        startingRects= set( freeRunsPerRow[currRow] )
        for b in currRects :
            brokenB= True
            for a in freeRunsPerRow[currRow] :
                modifiedContinuingRect, t_brokenB, t_absorbedA= intersect(a,b)
                if not modifiedContinuingRect.isEmpty() and not [ x for x in continuingRects if x.contains(modifiedContinuingRect) ] :
                    continuingRects-= { x for x in continuingRects if modifiedContinuingRect.contains(x) }
                    continuingRects|= {modifiedContinuingRect}
                if not t_brokenB : brokenB= False
                if t_absorbedA : startingRects-= {a}
            if brokenB and not b.isUnit() : yield b
        currRects= continuingRects
        currRects|= startingRects
    for b in currRects : 
        if not b.isUnit() : yield b

测试/示例

使用以下测试代码：

input= []
input.append("   X    ")
input.append("        ")
input.append(" X      ")
input.append("     X X")
input.append("        ")
input.append("        ")
input.append("    X   ")
input.append("   X  X ")
input.append(" X     X")

# Translates input into a list of coordinates of free elements
freeElements= []
for rowNum, row in enumerate(input):
    for colNum, element in enumerate(row):
        if element == " " :
            freeElements.append( (rowNum,colNum) )
for fe in freeElements :
    print( fe )

# Find and print open rectangles
for openRect in findOpenRectangles(freeElements,len(input)) :
    print( openRect )

输出如下（一些格式以节省空间和添加的标题）：

自由元素

(0, 0), (0, 1), (0, 2), (0, 4), (0, 5), (0, 6), (0, 7)
(1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7)
(2, 0), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7)
(3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 6)
(4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (4, 7)
(5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (5, 7)
(6, 0), (6, 1), (6, 2), (6, 3), (6, 5), (6, 6), (6, 7)
( 7, 0), (7, 1), (7, 2), (7, 4), (7, 5), (7, 7)
(8, 0), (8, 2), (8, 3 ), (8, 4), (8, 5), (8, 6)

freeRunsPerRow

(0, {Rect(Range(0,0),Range(0,2)), Rect(Range(0,0),Range(4,7))})
(1, {Rect(Range(1,1 ) ),Range(0,7))})
(2, {矩形(Range(2,2),Range(2,7)), 矩形(Range(2,2),Range(0,0))})
(3, {Rect(Range(3,3),Range(6,6)), Rect(Range(3,3),Range(0,4))})
(4, {Rect(Range(4,4 ) ),Range(0,7))})
(5, {Rect(Range(5,5),Range(0,7))})
(6, {Rect(Range(6,6),Range(5, 7)), 矩形(范围(6,6),范围(0,3))})
(7, {矩形(范围(7,7),范围(7,7)), 矩形(范围(7,7) ),范围(4,5)), 矩形(范围(7,7),范围(0,2))})
(8, {矩形(范围(8,8),范围(0,0)), 矩形（范围（8,8），范围（2,6））}）

findOpenRectangles(freeElements,len(input))

矩形(范围(0,1),范围(0,2))
矩形(范围(1,1),范围(0,7))
矩形(范围(0,2),范围(4,7))
矩形(范围（1,2），范围（2,7））
矩形（范围（3,5），范围（0,4））
矩形（范围（0,5），范围（4,4））
矩形（范围（ 4,5),范围(0,7))
矩形(范围(1,5),范围(2,4))
矩形(范围(1,6),范围(2,3))
矩形(范围(4, 6),范围(5,7))
矩形(范围(0,6),范围(6,6))
矩形(范围(3,6),范围(0,3))
矩形(范围(3,7) ,范围(0,2))
矩形(范围(4,7),范围(7,7))
矩形(范围(8,8),范围(2,6))
矩形(范围(7,8),范围(4,5))
矩形(范围(0,8),范围(2,2))
矩形(范围(4,8),范围(5,5))
矩形(范围(0,8),范围(0 ,0))

测试/示例结论

输出正确。所有非平凡的矩形都存在。

于 2013-08-30T19:13:38.647 回答
0

可用坐标列表已排序。

所以也有一个全局的，迄今为止最大的矩形，作为列表。

做一个列表遍历，并为每个项目调用一个函数，子列表从项目开始。查找从该项目左上角开始的最大矩形。

public List<Coord> getMaxRectangle(List<Coord> openCoords) {
    List<Coord> currentMaxRectangle = null;
    for (int i = 0; i < openCoords.size(); ++i) {
        // Handle all rectangles starting here:
        currentMaxRectangle = maxRectangleStartingAt(i, currentMaxRectangle);
    }
    return currentMaxRectangle;
}

public List<Coord> maxRectangleStartingAt(int i, List<Coord> openCoords) {
    // Now the interesting part:
    // Take the maximal width list first: standing for all widths 1, ... max width.
    List<Coord> rect = new ArrayList<>();
    for (int j = i; j < openCoords.size()
            && openCoords.get(j).y == openCoords.get(i).y
            && openCoords.get(j).x - openCoords.get(i).x == j - i;
            ++j) {
        rect.add(openCoords.get(j);
    }
    int maxWidth = rect.size();
    // Now we can look for next lines below rect.get(0), ... get(maxWidth - 1),
    // continuously diminishing maxWidth till 0.
    // When we need to diminish maxWidth, we can look wether the original
    // maxWidth by (currentY - 1) is a maximum result.
    ...
}

所以我们走：

           +-------------+ 1st rect
           |           |
           |           | 2nd rect
           |      | 3rd rect
           |   | 4th rect

O(N²) 复杂度的演示：

public static void main(String[] args) {
    int[][] openCoords = {
        {0, 2},
        {1, 0},
        {1, 1},
        {1, 2},
        {2, 0},
        {2, 1}
    };
    new MaxRectFinder().find(openCoords);
}

private int[] maximumTopLeft;
private int[] maximumSize;

private void find(int[][] openCoords) {
    maximumTopLeft = null;
    maximumSize = new int[2];
    for (int topLeftCandidateI = 0; topLeftCandidateI < openCoords.length; ++topLeftCandidateI) {
        int yOrig = openCoords[topLeftCandidateI][0];
        int xOrig = openCoords[topLeftCandidateI][1];
        int y = yOrig;
        int x = xOrig + 1;
        int j = topLeftCandidateI + 1;
        while (j < openCoords.length
                && openCoords[j][0] == y
                && openCoords[j][1] == x) {
            ++x;
            ++j;
        }
        // Now we have a maximum x.
        for (;;) {
            // Skip after right side on current line:
            while (j < openCoords.length
                    && openCoords[j][0] == y) {
                ++j;
            }
            ++y;
            // Check for maximum:
            if (maximumTopLeft == null || (y - yOrig)*(x - xOrig) > maximumSize[0] * maximumSize[1]) {
                maximumSize[0] = y - yOrig;
                maximumSize[1] = x - xOrig;
                maximumTopLeft = openCoords[topLeftCandidateI];
            }
            // Skip before left side below origin:
            while (j < openCoords.length
                    && openCoords[j][0] == y
                    && openCoords[j][1] < x) {
                ++j;
            }
            if (j >= openCoords.length
                    || openCoords[j][0] != y
                    || openCoords[j][1] != x) {
                break;
            }
            // Register rectangle part:
            int x2 = xOrig;
            while (j < openCoords.length
                    && openCoords[j][0] == y
                    && openCoords[j][1] == x2
                    && x2 <= x) {
                ++x2;
                ++j;
            }
            x = x2;
        }
    }
    if (maximumTopLeft == null) {
        System.out.println("No solution found, not even 1x1.");
    } else {
        System.out.printf("At [%d, %d] with size [%d, %d].%n",
                maximumTopLeft[0], maximumTopLeft[1], maximumSize[0], maximumSize[1]);
    }
}
于 2013-08-29T17:00:02.540 回答