[m0nzt3r]

Здравствуйте. Есть поле M*N. Есть Q фигур. Нужно для всех возможных расстановок этих Q фигур выполнить над матрицей (полем) некие операции. Подскажите идею, как реализовать перебор возможных комбинаций.

Поле - целочисленная матрица. Фигуры - определенное число. Переставлять нужно в области, ограниченной крайними столбцами/строками, исключая их. Своеобразную "рамочку" не трогать.

Спасибо заранее.

[Страдалецъ]

3D-тетрис что-ли делаете?

[m0nzt3r]

Не, не тетрис. Кстати, расставляемые элементы - одинаковы. То бишь главное факт занимания ими ячейки, а в каком они порядке - не важно. Главное, чтобы все три были в трех разных местах. Суть - генерация всевозможных лабиринтов с Q закрашенными ячейками.

[s0Creator]

Т.е. Q меньше M*N и должны быть все расположены, каждая один раз - вот это перебрать ?

[m0nzt3r]

Сообщение от s0Creator

Т.е. Q меньше M*N и должны быть все расположены, каждая один раз - вот это перебрать ?

Угу, все так и есть.

[s0Creator]

С учетом того, что любой ячейке можно сопоставить число от 0 до (M*N-1) [i + j*M]. технология где-то так:
Массив размерностью Q ( ms[0] определяет положение первого элемента, ms[1] второго ...)
А дальше перебор с вложенностью Q
Т.е для каждого ms[0] (от 0 до (M*N-1) ) перебор всех ms[1] (от 0 до (M*N-1) ) где ms[0] <> ms[1]
для этой пары соответственно ms[2] (от 0 до (M*N-1) ) где ms[2]<>ms[0] и ms[2]<>ms[1].
По идее можно сделать универсальный алгоритм ( функцию )

[s0Creator]

А наложить его потом на внутреннюю область думаю не трудно будет.
Если например принять что [0,0] соответствует [2,2] то [i,j] соотв. [i+2,j+2].

[m0nzt3r]

Уфф, что-то сложновато. Завтра попробую перечитать и осмыслить.

[s0Creator]

Набросал немного с использованием классов ( смотри UPerebor.pas )

Думаю еще попробовать попозже реализацию последевательного построения карты разными типами фигур ( если конечно стоит )
Или лучше попробовать перебор на карте с произвольно расположенными препятствиями ( Map[Row, Col] = 0 значит ячейка свободна ).
И заметил что надо заменить

PHP код:

function TFigursPerebor.First: Boolean;
var
  i, n: Integer;
begin {$BOOLEVAL OFF}
  Result := false;
  if (FArrLen < FCount) or (FCount <= 0) then
    Exit; // < фигуры не помещаются или их 0
  SetLength(FFigurs, FCount);
  n := 0;
  for i := 0 to FCount - 1 do
  begin
    FFigurs[i] := n;
    if (not CheckByIndex(i)) and (not IncByIndex(i)) then 
      Exit; // < это на будущее ( для произвольных препятствий )
    n := FFigurs[i] + 1;
  end;
  Result := true;
end; 


Он сделан с расчетом на будущее