Упаковка квадратов фиксированного размера на сетке с препятствиями - PullRequest
Новая
       35

Упаковка квадратов фиксированного размера на сетке с препятствиями

0 голосов
/ 26 ноября 2018

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

Пример сетки с черными ячейками, представляющими пустое пространство, и красными ячейками, представляющими препятствия.Далее приведен пример решения с несколькими желтыми квадратами 5x5, найденными в сетке:

enter image description here enter image description here

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

var width = 10, height = 10;
var grid = new Array(width * height);
var sizes = new Array(width * height);

function findBiggestSquare() {
    var bestSize = -1, bestLocation = -1;

    for (var i = grid.length - 1; i >= 0; i--) {
        var size = 0;

        if (grid[i] === 0) {
            size = 1 + Math.min(sizes[i+1], sizes[i+width], sizes[i+1+width]);

            if (size > bestSize) {
                bestSize = size;
                bestLocation = i;
            }
        }

        sizes[i] = size;
    }

    if (bestLocation !== -1)
        return {'size': bestSize, 'location': bestLocation};
    else
        return null;
}

1 Ответ

0 голосов
/ 26 ноября 2018

Вы можете легко найти все потенциальные центры таких квадратов, проверив наличие препятствий в каждой части NxN сетки.Некоторые прямые оптимизации могут быть сделаны.Вот ваш пример с потенциальными центрами оранжевого цвета:

highlighted potential centers

Хотя выделение центральной ячейки легче визуализировать, вы можете работать с углом,Таким образом, вам не нужно беспокоиться о четности N, а остальное может быть более простым.

После того, как у вас есть эти выделенные ячейки, присвойте каждому номер, равный количеству других выделенных ячеек.клетки, которые были бы недоступны, если вы поставите квадрат.Например, если у вас есть список потенциальных левых верхних углов, число, назначенное одному из них, является числом потенциальных левых верхних углов в квадрате 2*N-1 с центром в нем.

Затем выберитеячейку с наименьшим числом, чтобы поставить квадрат, и обновите сетку соответственно.Повторяйте, пока ваш список не станет пустым.

...