My brain is already boiling... And I can't figure out the algorithm for the following:

And so, there is a grid of cells/pixels/squares, etc. (something else!):

Have all the squares (red) to place on each other at the bottom.

Everything seems to be simple but there is one thing. There is a minimum quantity squares, some of which may not be lower or higher than the other.

For example:

The squares in the cell [5,2] and [5,3] will go down by 1 cell down on the y axis.

Then we solder the square must fall on two cells down.

In the end it should look like this:

If it were not for minimum quantity of squares, then the solution would be simple:

Pass the loop along the X-axis, and each cell (X-axis) check all cells on the y-axis (upward). Consider the number of empty cells to the square and drop the square down on the counted number of empty cells.

But what about the soldered squares?

And so, there is a grid of cells/pixels/squares, etc. (something else!):

Have all the squares (red) to place on each other at the bottom.

Everything seems to be simple but there is one thing. There is a minimum quantity squares, some of which may not be lower or higher than the other.

For example:

The squares in the cell [5,2] and [5,3] will go down by 1 cell down on the y axis.

Then we solder the square must fall on two cells down.

In the end it should look like this:

If it were not for minimum quantity of squares, then the solution would be simple:

Pass the loop along the X-axis, and each cell (X-axis) check all cells on the y-axis (upward). Consider the number of empty cells to the square and drop the square down on the counted number of empty cells.

But what about the soldered squares?

asked July 9th 19 at 11:04

5 answers

answered on July 9th 19 at 11:06

First allocate connected pieces.

Initially, each individual square and each figure marked "free."

In a loop until there are free squares:

check all squares-if a square floor or a "frozen" square, frost it;

check for loose figures, if the figure appeared frozen squares, frost figure and the rest of the squares in the figure;

check free figures, each square of it drop 1 square down;

go to the beginning of the cycle.

If the field is very large, you can try to calculate more efficiently. But it need to bother. The idea is that you can run on the columns to evaluate how the pieces move relative to each other. And then see how they can all be omitted. But then what to do XS =)

Initially, each individual square and each figure marked "free."

In a loop until there are free squares:

check all squares-if a square floor or a "frozen" square, frost it;

check for loose figures, if the figure appeared frozen squares, frost figure and the rest of the squares in the figure;

check free figures, each square of it drop 1 square down;

go to the beginning of the cycle.

If the field is very large, you can try to calculate more efficiently. But it need to bother. The idea is that you can run on the columns to evaluate how the pieces move relative to each other. And then see how they can all be omitted. But then what to do XS =)

answered on July 9th 19 at 11:08

010

010

010

It's a stick. The other figures can do the same. And kolsite units.

010

010

It's a stick. The other figures can do the same. And kolsite units.

Can be a little bit more? Example, for example. :) - Gisselle.Sporer commented on July 9th 19 at 11:11

answered on July 9th 19 at 11:10

Pass the loop along the X-axis, and each cell (X-axis) check all cells on the y-axis (upward). Consider the number of empty cells to the square and drop the square down on the counted number of empty cells.

Why did you omit columns? Lower line, pass the loop from the bottom up and itenerate as long as there will be changes.

Yeah, thought so, but the fact that the squares can be soldered both horizontally and vertically simultaneously with a large number of squares. For example that is something like this:

┌─┐ ┌─┐

└─┘ └─┘

┌─┐┌─┐┌─┐┌─┐

└─┘└─┘└─┘└─┘

┌─┐

└─┘ commented on July 9th 19 at 11:13

┌─┐ ┌─┐

└─┘ └─┘

┌─┐┌─┐┌─┐┌─┐

└─┘└─┘└─┘└─┘

┌─┐

└─┘ commented on July 9th 19 at 11:13

Well, going from the bottom up, came across the square, runs the method of "lowering block":

1) if a square is "stuck neighbor", see if there's an empty space under the square.

1A) there is no space, leave the method (you can mark the coordinates of that block as unusable for lowering and not check them)

1B) there is room, check the availability below for "stuck neighbor", etc.

1B) there is a place for all the "sticky neighbors" - shift them all down one cell and run the method again.

2) "stuck neighbor" no - run simplified method for lowering the block (checks for empty space just under the current square and lower it while you can).

3) PROFIT!

P. S. a test job or what? commented on July 9th 19 at 11:16

1) if a square is "stuck neighbor", see if there's an empty space under the square.

1A) there is no space, leave the method (you can mark the coordinates of that block as unusable for lowering and not check them)

1B) there is room, check the availability below for "stuck neighbor", etc.

1B) there is a place for all the "sticky neighbors" - shift them all down one cell and run the method again.

2) "stuck neighbor" no - run simplified method for lowering the block (checks for empty space just under the current square and lower it while you can).

3) PROFIT!

P. S. a test job or what? commented on July 9th 19 at 11:16

: Add in check for free space at the bottom should not be included "stuck neighbors" of the same unit. I.e. if the scan shows that the bottom non-empty cell, and "stuck neighbor" - believe that the place is.

You have at this point the difficulty was?)) commented on July 9th 19 at 11:19

You have at this point the difficulty was?)) commented on July 9th 19 at 11:19

: there is not so simple. Imagine two figures in the form [ and] geared to each other. They will remain up, leaning on each other, and must fall as a whole. commented on July 9th 19 at 11:22

: well then just add a condition - we assume that if one unit somehow relies on the other - that's one common block)) commented on July 9th 19 at 11:25

answered on July 9th 19 at 11:12

This is the usual Tetris in space.

First raise all the shapes and fill up line by line.

If you need better - is combinatorics.

First raise all the shapes and fill up line by line.

If you need better - is combinatorics.

answered on July 9th 19 at 11:14

Pass the loop along the X-axis, and each cell (X-axis) check all cells on the y-axis (upward).

Imagine knit figure in the form of a ladder of squares. While it is soldered as a whole. And how are you going to check?

Then you need the very figure to make an object that consists of squares. And each square needs to know whether it is possible to move in any direction. Then to move the entire figure, it will just poll all your squares.

Find more questions by tags ProgrammingAlgorithms