Что такое алгоритм возврата свободного пространства в блоках максимально возможных прямоугольников?

Ответ 1

Из вашего примера видно, что вы не просите исключить перекрытие (например, 1 и 2 имеют общий левый сегмент), поэтому, возможно, это будет соответствовать вашим потребностям:

• Разделите пространство на прямоугольники на основе углов, обозначенных занятыми пространствами.

• Формируйте "основные прямоугольники", расширяя отрезки от этих углов до краев всего пространства.

• Используя любой систематический порядок (например, сверху вниз, слева направо):

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

  3,2. Составьте набор всех (уникальных) таких расширенных прямоугольников.

Обратите внимание, что это поиск/сборка основывается на "основных прямоугольниках" с шага 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

     }

  }

}

Это самый простой и прямой способ сделать это. но плохой момент состоит в том, что он должен пересекать все пространство, которое может вызвать неэффективность.

Самодельное:

• (STEP1) цикл через все строки, в то время как строки пустые
• (STEP1) останавливается, когда занятое пространство находится в строке
  • (STEP1) сохраняет значение текущей строки TOP_EMPTY только в первый раз
• (STEP2), если число оставшихся строк - это число столбцов, перейдите к шагу 8
• (STEP2) цикл через оставшиеся строки
• (STEP2) вычислить пространство перед занятым пространством
• (STEP2) вычислить пространство за занимаемым пространством
• (STEP2) конец цикла
• (STEP2) перейти к 13
• (STEP2) цикл через столбцы
• (STEP2) пропустить строки TOP_EMPTY
• (STEP2) вычислить пространство перед занимаемым пространством в столбце
• (STEP2) вычислить пространство после занимаемого пространства в столбце
• (STEP2) конец цикла
• (STEP3) вычислить пространство вверху с помощью TOP_EMPTY * no. столбцов
• DONE.

Ответ 3

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;

update: java code.

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

Ответ 4

• Начало
• set row = 0, column = 0
• if - свободное пространство:
  • получить наибольший свободный прямоугольник, начиная горизонтально
• если нет, а в последнем столбце, а не в конце, строка + 1, столбец = 0 и goto 3
• else, если не последний столбец, столбец + 1 и goto 3
• else end

(заметим, что 3.1 - тот же алгоритм, только со свободным/заблокированным перевернутым и с разными координатами)

Ответ 5

Вы ищете нечто похожее на Code Golf: Runwater Water

Ответ 6

Я думаю, что рассмотреть, что только программисты не получат лучшую математику.

Например, на изображении ниже "r" rect является наилучшим совпадением, но не начинается в любом углу.

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

Ответ 7

Я думаю, что вы можете реализовать подход Montecarlo.

С уважением.