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

1. Начало
2. установить строку = 0, столбец = 0
3. , если есть свободное место:
   1. получить наибольший свободный прямоугольник, начиная по горизонтали
4. , если нет, и в последнем столбце, но не в конце, строка + 1, столбец = 0 и перейти к 3
5. иначе, если не в последнем столбце, столбец + 1 и goto 3
6. else end

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

Простите за ввод кодов:

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. ( ШАГ1 ) сохранить значение текущей строки в TOP_EMPTY только в первый раз
3. ( ШАГ2 ), если количество оставшихся строк> количества столбцов, перейти к шагу 8
4. ( STEP2 ) цикл по оставшимся строкам
5. ( STEP2 ) вычисляет пространство перед занятым пространством
6. ( STEP2 ) вычисляет пространство позади занятое пространство
7. ( STEP2 ) конец цикла
8. ( STEP2 ) перейти к 13
9. ( STEP2 ) цикл через столбцы
10. ( ШАГ2 ) пропустить строки TOP_EMPTY
11. ( ШАГ2 ) вычислить пространство перед занятым пространством в столбце
12. ( ШАГ2 ) вычислить пространство после занятого места в столбце
13. ( STEP2 ) конец цикла
14. ( STEP3 ) вычислите пространство вверху с TOP_EMPTY * no.столбцов
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;
    }
}

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

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

С уважением.