返回最大可能矩形块中的可用空间的算法是什么?

从您的示例中,您似乎没有要求排除重叠(例如,1和2具有相同的左上部分),因此这可能适合您的需要:

1. 根据所占空间标识的角将空间划分为矩形。

2. 通过将线段从这些角延伸到整个空间的边缘,形成“基本矩形”。

3. 使用任何系统顺序(例如从上到下、从左到右):

   3.1。选择一个基本矩形,并将其尽可能扩展到具有共同边的其他基本矩形。

   3.2.形成所有(唯一)扩展矩形的集合。

请注意,这个搜索/构建基于步骤2中的“基本矩形”,而不是在整个空间中逐点进行,因此性能应该更好。

请原谅我用密码写:

for(int y = 0; y < rows; y++){

  for(int x = 0; x < columns; x++){
     // (x, y) would be the current space

     if(checkEmptySpace(x,y)){
       // empty space found

     }

  }

}

这是最简单直接的方法。但缺点是,它必须循环通过所有可能导致效率低下的空间。

即兴创作:

1. ( STEP1 )当行为空时循环遍历所有行
2. ( STEP1 )在行中找到占用空间时停止
   1. ( STEP1 )仅在第一次将当前行的值存储到“顶空”
3. ( 第二步 )如果剩余行数为>列数,请转到步骤8。
4. ( 第二步 )循环浏览其余行
5. ( 第2步 )计算占用空间前面的空间
6. ( 第二步 )计算占用空间后的空间
7. ( 第二步 循环结束
8. ( 第2步 转到13
9. ( 第二步 )循环浏览列
10. ( 第二步 )跳过顶部空行
11. ( 第二步 )计算列中占用空间之前的空间
12. ( 第二步 )计算列中占用空间后的空间
13. ( 第二步 循环结束
14. ( 步骤3 )计算顶部有空*列数的顶部空间
15. 完成。

char mark = 'A';
for(i from 0 to rows)
    colstart = 0;
    while(colstart = next empty col in ith row)
        width = 0;
        for(j from colstart to columns)
        {
            if(empty)
                width++;
            else 
                break;
        }
        if(width == 0)
            continue
        for(n from colstart to colstart + width)
            for(m from i to rows)
                if(!empty)
                    break;
            if(m != i)
                set the rectangle from i, colstart to m - 1, colstart + width 
                with mark char and increment mark;

更新:Java代码。

public class Program
{
    public static char occuppied;
    public static char vacant;
    public static char mark;
    public static void main(String[] args)
    {
        int rows = 7;
        int cols = 11;
        mark = 'A';
        occuppied = '#';
        vacant = '-';
        char[][] matrix = new char[rows][cols];
        setRect(matrix, vacant, 0, 0, rows, cols);
        setRect(matrix, occuppied, 3, 3, 2, 2);
        setRect(matrix, occuppied, 5, 5, 2, 6);

        print(matrix);
        for(int i = 0; i < rows; i++)
        {
            int colstart = 0;
            while((colstart = nextEmptyCol(matrix[i], colstart)) != -1)
            {
                int width = 0;
                for(int j = colstart; j < cols; j++)
                {
                    if(matrix[i][j] == vacant)
                        width++;
                    else
                        break;
                }
                if(width == 0)
                    continue;
                int height = 1;
                outer:
                for(; height + i < rows; height++)
                    for(int n = 0; n < width; n++)
                    {
                        if(matrix[i + height][colstart + n] == occuppied)
                            break outer;
                    }
                System.out.println("width = " + width + ", height = " + height);
                setRect(matrix, mark, i, colstart, height, width);
                print(matrix);
                mark++;
            }
        }
    }
    public static void setRect(char[][] matrix, char c, int startrow, int startcol, int numrows, int numcols)
    {
        for(int i = 0; i < numrows; i++)
            for(int j = 0; j < numcols; j++)
                matrix[startrow + i][startcol + j] = c;
    }
    public static void print(char[][] matrix)
    {
        int rows = matrix.length;
        int cols = matrix[0].length;
        for(int i = 0; i < rows; i++)
        {
            for(int j = 0; j < cols; j++)
                System.out.print(matrix[i][j] + " ");
            System.out.println();
        }
        for(int i = 0; i < cols; i++)
            System.out.print("==");
        System.out.println();
    }
    public static int nextEmptyCol(char[] row, int start)
    {
        for(int i = start; i < row.length; i++)
            if(row[i] == vacant)
                return i;
        return -1;
    }
}

1. 起点
2. 设置行=0,列=0
3. 如果是可用空间:
   1. 获取最大的可用矩形,从水平方向开始
4. 如果不是,则在最后一列,而不是在末尾,行+1,列=0,转到3
5. 否则,如果不是最后一列,则列+1和转到3
6. Else结束

(请注意,3.1是相同的算法,只有在自由/阻塞反向的情况下,并且坐标不同)

你在找类似的东西 Code Golf: Running Water

我认为,考虑到仅仅是Conrers不会得到最好的数学。

例如,在下面的图像中,“r”rect是最佳匹配,但不会从任何角开始。

+-------------+
|    rrrr     |
|+--+rrrr +--+|
||##|rrrr |##||
||##|rrrr |##||
||##|rrrr |##||
||##|rrrr |##||
|+--+rrrr +--+|
|    rrrr     |
+-------------+

我认为你可以实现 Montecarlo Approach .

当做。