Здравствуйте, Linuxoid, Вы писали:
L>Как определить число видов полиминошки? Под "видом" понимается положение фигуры, полученное поворотом на 90 град. или отражением относительно горизонтальной/вертикальной оси, но, естественно, не сдвигом (иначе число видов будет бесконечным ).
Сначала определим, сколько и каких вариантов бывает вообще.
Повороты и отражения совершаются с помощью матрицы преобразования координат. M=((x1,y1),(x2,y2)).
Сколько таких матриц всего?
Z = ((+/-1, 0), (0, +/-1)) -- отражения
R = ((0, +/-1), (+/-1, 0)) -- поворот на 90 + отражения
итого 8 вариантов.
Для фигуры определим ее размеры по X и по Y.
Если X != Y --- то варианты R отпадают, это очевидно.
Для каждой клеточки прямоугольника X*Y (и даже — для каждой клеточки полимино) находим координаты точек, симметричных ей (согласно доступным матрицам преобразований). Находим значения этих точек (есть/нет клеточка полимино).
Получаем вектор из 8 (или 4) булевских значений.
Поэлементная конъюнкция векторов для всех точек полимино покажет, какие варианты совпали с оригиналом, т.е. где есть симметрия.
Теперь считаем 8 — число симметрий.
Это и будет число вариантов.