CODEWITHSUNDEEP
algorithmtiles
Francesco
Francesco

Reputation: 85

Square tiles merging algorithm

I have an 8x8 square board on which there can be any combination of SQUARE tiles of different colors. These square tiles can be of different sizes, we can have squares of side ranging from 1 to 8, 8 being the max value due to the size of the board.

I need to find an algorithm that allows me to replace square areas of the same color with a square tile as big as the area itself.

See the examples below:

Click here to see an example

In these examples, we are changing the color of the tile marked with 'x' to yellow in order to obtain a bigger square yellow area. I am looking for an algorithm that will replace the big yellow square area with a corresponding tile of the same size as the area itself (step C). Perhaps the algorithm could start checking for neighboring tiles starting from the tile that we change the color of (the one marked with 'x').

Upvotes: 3

Views: 2200

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

With such a small board, perhaps we can use brute force. Iterate over the possible squares in descending order of size like so.

for (int width = 8; width > 0; width--) {
    for (int x0 = 0; x0 <= 8 - width; x0++) {
        for (int y0 = 0; y0 <= 8 - width; y0++) {
            int x1 = x0 + width;
            int y1 = y0 + width;
            ...
        }
    }
}

For each existing square S, test whether the candidate square [x0, x1] * [y0, y1] intersects S, and if so, whether it contains S. If S intersects but is not contained, then [x0, x1] * [y0, y1] is not a possible replacement. If S is contained but has the wrong color, ditto.

If candidate survives these tests (and contains the changed square, in case the original board has more tiles than it should), then it is placed, and the squares it contains are deleted.

Upvotes: 2

Related Questions