CODEWITHSUNDEEP
algorithmmatrixlanguage-agnosticdynamic-programming
HankMoody
HankMoody

Reputation: 3174

Fixed-size squares packing on a grid with obstacles

I'm searching for an algorithm that would find all non-overlapping squares of given size in a grid with obstacles. All squares must have the same size, which would be given as one of the inputs.

Example grid with black cells representing empty space and red cells representing obstacles. Next is an example solution with multiple 5x5 yellow squares found in the grid:

enter image description here enter image description here

What I have so far is an algorithm that finds biggest square using dynamic programming, but I don't know if it will be useful for the above problem. Maybe it could be modified to find multiple squares.

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

Upvotes: 0

Views: 361

Answers (1)

Nelfeal
Nelfeal

Reputation: 13269

You can easily find all the potential centers of such squares by checking for obstacles in each NxN portions of the grid. Some straightforward optimizations can be done. Here is your example with the potential centers in orange:

highlighted potential centers

Although picking the central cell is easier to visualize, you may want to work with a corner. That way, you don't have to worry about the parity of N, and the rest might be more straightforward.

Once you have these highlighted cells, assign a number to each one equal to the number of other highlighted cells that would be unavailable if you put a square there. For example, if you have the list of potential top-left corners, the number assigned to one of them is the number of potential top-left corners in a 2*N-1 square centered on it.

Then, pick the cell with the lowest number to put a square on, and update the grid accordingly. Repeat until your list is empty.

Upvotes: 1

Related Questions