Заполнение сетки неизвестными фигурами

Question

В качестве входных данных я даю 2D сетку из 0 с несколькими позициями -1, указывающими места, которые не могут быть заполнены, и чертеж некоторых фигур (как в игре Tetris)

 ex. of grid              ex. of shapes

 0  0  0  0  0  0  0        1 1 1     2 2 2     3 3
-1  0  0  0  0  0  0        1           2
-1  0  0  0  0  0  0        1
 0  0  0  0  0 -1  0
 0  0  0 -1  0  0  0

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

Answer 1

Это моя мысль о том, как мне решить эту проблему:

Кажется, что для каждой фигуры существует 4 возможных типа (включая оригинал):

1 1 1          1    1 1 1    1
1       ->     1        1    1
1          1 1 1,       1,   1 1 1 

Теперь давайтескажем, есть s количество фигур, тогда есть 4s всего фигур.

Возьмите комбинацию из 4s фигур и сформируйте фигуру, такую ​​как:

  2
1 2 2
1 2 3 3
1 1 1 

или

1 1 1
1 2 3 3
1 2 2
  2 

или

1 1 1 3 3
1 2 2 2
1   2

или

любая такая цифра из (4s)^2 = 16s^2 возможностей.

На самом деле это больше, чем 16s^2потому что это не просто объединение форм, вам нужно жадно искать свободные места и пытаться вписаться в них.: (

Теперь у вас есть фигура в вашей руке, ищите ту же форму в вашей сетке.

Так, например, для поиска

1 1 1
1 2 3 3
1 2 2
  2 

Я бы посмотрелдля

0 0 0
0 0 0 0
0 0 0
  0 

в исходной сетке.

Тогда возникает проблема с нахождением этой цифры в исходной матрице.

Также см. this , который похож на вопрос, но не совсем тот же, о поиске фигур.