Вот до такой строчки мой комп додумался сегодня ночью
Не сам, конечно, а после сильной переработки кода. По сравнению с ранее опубликованным всё бегает раз в 15 быстрее. Прога по-прежнему нагружает только проц. Можно перевести её в низкий приоритет и комфортно работать на компе. И лет через 8 я достигну инетовского рекорда 28
Замечательно, что ускорение совпало с сильным
упрощением текста. Пропало сложное и немного искусственное понятие "кодирующей последовательности". Две функции слились в одну весьма прозрачную, рекурсивную, как и просилось сразу. Она
ровно по разу обходит все полимино порядка n и считает их, а заодно (почти без потерь времени) и все меньшие порядки.
После ускорения перебора в полный рост встал вопрос об ускорении отсеивания отражений (который раньше был не критичен). Здесь крайне своевременной оказалась идея МихаилаП о "центре тяжести". (В моём воспалённом мозгу она тоже бродила, но давно и не столь ясно.) Забавно, что при внешней простоте, идея потребовала очень аккуратной реализации — я долго не мог добиться одновременно верного ответа и ясного понимания, что делаю. (Хотя порознь было много раз
)
Ниже приведён код, который можно откомпилировать и поиграться (даже порисовать). Я нахожу его совершенным
и потому больше не буду терроризировать ни себя ни вас.
Если кому-то удастся серьёзно ускорить, оценку обещаю
Пояснять код нет большого смысла, тем более, что там половина строк комментарии.
// Polymino.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <stdlib.h>
//максимальный порядок полимино
#define N 33 //странная цифра, но почему нет :-)
//если не жалко времени, можно рисовать полимино
//либо для всех порядков либо только для старшего
//причём выводим не в банальный столбик, а в строчку ;-)
//#define NEED_DRAW_ALL
//#define NEED_DRAW_HIGH
#if defined NEED_DRAW_ALL || defined NEED_DRAW_HIGH
char out[N+1][80]={0};
#endif
//4 возможных направления движения
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
char board[N+1][2*N-2];
// полимино в раскодированном виде, удобном для отражений
//поле битвы и результат работы основной функции Enum()
//матрица [y][x], в ячейках одно из 3-х значений:
//-1 - запрет - точно нет заполненной клетки
// 1 - стоит - точно есть заполненная клетки
// 0 - туман - пока неизвестно, есть ли клетка
int x1,x2,y1,y2;//границы полимино, лежащего в board[][]
int x0,y0; //а здесь лежать суммы всех x и y для вычисления среднего
//довесок к board - перспективы заполнения
int fifo_x[N-1];
int fifo_y[N-1];
int fifo_tail=0;
int fifo_head=0;
int n; //порядок полимино (цель)
int k; //сколько клеток уже поставлено
__int64 countTotal[N], countMain[N];//здесь будем считать,
//причём сразу оба (всего и без отражений) и для всех порядков
//вспомогательная функция для отсеивания отражений
bool IsMainBoard();
//основная рекурсивная функция
//в результате её работы вглубь от k=0 до k=n
//в board последовательно перебывают ровно по одному разу (!)
//все полимино порядка не больше n (вообще все, с отражениями)
//стартуя с того, что сейчас лежит в board+fifo+k
//подсчитывет число продолжений до порядка n
//в результате board+fifo+k остаётся без изменений (!)
void Enum()
{
if(k==0) //первый вход
{
memset(countTotal,0,sizeof(countTotal));
memset(countMain ,0,sizeof(countMain ));
memset(board, 0,sizeof(board)); //заполняем всё туманом
memset(board,-1,sizeof(board[0][0])*(3*N-4)); //заполняем начало запретами
//поставим первую клетку
fifo_x[0]=N-2;
fifo_y[0]=1;
fifo_tail=1;
fifo_head=0;
board[fifo_y[0]][fifo_x[0]]=1;
x0=x1=x2=fifo_x[0];
y0=y1=y2=fifo_y[0];
k=1;
Enum();
k=0; //board+fifo можно не восстанавливать -
return; //при следующем входе всё равно обнулим
}
int save_fifo_head=fifo_head; //сохраним чтобы потом вернуть
while(fifo_tail>fifo_head) //перебор возможностей поставить
{
for(int d=0;d<4;d++) //ищем самую первую возможность
{
int y=fifo_y[fifo_head]+dy[d];
int x=fifo_x[fifo_head]+dx[d];
if(board[y][x]==0) //точка в тумане - нашли !
{
board[y][x]=1; //сначала попробуем сюда поставить
k++;
int save_y2=y2;//поправим границы
int save_x1=x1;
int save_x2=x2;
if(y>y2) y2=y;
if(x<x1) x1=x;
if(x>x2) x2=x;
x0+=x;
y0+=y;
//помещаем поставленную клетку в очередь
fifo_y[fifo_tail]=y;
fifo_x[fifo_tail]=x;
fifo_tail++;
countTotal[k]++;
if(IsMainBoard())
{
countMain[k]++;
#ifdef NEED_DRAW_HIGH
if(k==n)
#endif
#if defined NEED_DRAW_ALL || defined NEED_DRAW_HIGH
{
if(strlen(out[0])+n+1>75)
for(int y=0;y<n+1;y++)
printf("%s\n",out[y]),out[y][0]=0;
for(int y=1;y<n+1;y++)
for(int x=0;x<n+1;x++)
strcat(out[y-1],board[y][x1+x]==1? "\1":" ");
}
#endif
}
if(k<n) //продолжение банкета
Enum(); //сколько развитий при поставленной
//теперь попробуем наоборот запретить
board[y][x]=-1;
k--;
//вернём границы
y2=save_y2;
x1=save_x1;
x2=save_x2;
x0-=x;
y0-=y;
//убираем из очереди
fifo_tail--;
Enum(); //сколько развитий при запрещённой
//наконец, не забудем отыграть всё обратно
board[y][x]=0;
fifo_head=save_fifo_head;
return; //никакого цикла реально нет -
//нашли первую возможность и либо ставим либо нет
}
}
//из этой фишки идти уже некуда - идём к следующей
fifo_head++;
}
//не нашли ни одной возможности, куда бы поставить
//возвращаем всё как было и уходим
fifo_head=save_fifo_head;
#if defined NEED_DRAW_ALL || defined NEED_DRAW_HIGH
if(k==1)//конец игре - распечатаем остаток
for(int y=0;y<n+1;y++)
printf("%s\n",out[y]),out[y][0]=0;
#endif
}
//возвращает true если в board находится "правильно" повёрнутая конфигурация
//"правильность" можно задавать довольно произвольно, важно чтобы однозначно -
//среди всех 8 отражений должно быть ровно 1 правильное
//эта реализация обычно проверяет попадание центра тяжести в нужную восьмушку
//и только в пограничных случаях врубает полную мощь вычислений
//можно попробовать поулучшать, но ускорить вдвое - это вряд ли
bool IsMainBoard()
{
int bx=x0*2-(x1+x2)*k;
int by=y0*2-(y1+y2)*k;
if(bx==0 && by<0)
{
//проверка, а не симметричная ли фигура относительно вертикали
int ny=y2-y1, nx=x2-x1;
for(int y=0;y<=ny;y++)
for(int x=0;x<(nx+1)/2;x++)
{
if(board[y1+y][x1+x]==1 && board[y1+y][x1+nx-x]!=1)
return true;
if(board[y1+y][x1+x]!=1 && board[y1+y][x1+nx-x]==1)
return false;
}
return true;
}
else if(bx<0 && by==bx)
{
//проверка, а не симметричная ли фигура относительно диагонали
int ny=y2-y1, nx=x2-x1;
if(nx<ny)
return false;
if(nx>ny)
return true;
for(int y=0;y<=ny;y++)
for(int x=0;x<y;x++)
{
if(board[y1+y][x1+x]==1 && board[y1+x][x1+y]!=1)
return true;
if(board[y1+y][x1+x]!=1 && board[y1+x][x1+y]==1)
return false;
}
return true;
}
else if(bx==0 && by==0)
{
int ny=y2-y1, nx=x2-x1;
if(nx<ny)
return false;
int reflect_impossible[2][2][2]={0};//[x<->y][y<->ny-y][x<->nx-x]
for(int y=0;y<=ny;y++)
for(int x=0;x<=nx;x++)
{
if(1==board[y1+y][x1+x])
{
if(1!=board[y1+y ][x1+nx-x]) reflect_impossible[0][0][1] =1;
if(1!=board[y1+ny-y][x1+x ]) reflect_impossible[0][1][0] =1;
if(1!=board[y1+ny-y][x1+nx-x]) reflect_impossible[0][1][1] =1; if(nx==ny) {
if(1!=board[y1+x ][x1+y ]) reflect_impossible[1][0][0] =1;
if(1!=board[y1+x ][x1+nx-y]) reflect_impossible[1][0][1] =1;
if(1!=board[y1+nx-x][x1+y ]) reflect_impossible[1][1][0] =1;
if(1!=board[y1+nx-x][x1+nx-y]) reflect_impossible[1][1][1] =1; }
}
else if(1==board[y1+y ][x1+nx-x] && reflect_impossible[0][0][1]==0 ||
1==board[y1+ny-y][x1+x ] && reflect_impossible[0][1][0]==0 ||
1==board[y1+ny-y][x1+nx-x] && reflect_impossible[0][1][1]==0 || nx==ny && (
1==board[y1+x ][x1+y ] && reflect_impossible[1][0][0]==0 ||
1==board[y1+x ][x1+nx-y] && reflect_impossible[1][0][1]==0 ||
1==board[y1+nx-x][x1+y ] && reflect_impossible[1][1][0]==0 ||
1==board[y1+nx-x][x1+nx-y] && reflect_impossible[1][1][1]==0 ) )
{
return false;
}
}
return true;
}
//почти всегда доходим до этого места, особенно для больших порядков
if(bx<0 && by<bx)
return true; //здесь выходим примерно 1/8 случаев
return false; //здесь выходим примерно в 7/8 случаев
}
int main(int argc, char* argv[])
{
while(1)
{
char s[80];
gets(s);
n=atoi(s);
if(n<1 || n>31)
{
printf("Enter a polyominoe size 0<N<32\n\n");
continue;
}
printf("--\n");
k=0;Enum();
printf("\n");
for(k=2;k<=n;k++)
{
char s1[80],s2[80];
_i64toa(countTotal[k],s1,10);
_i64toa(countMain [k],s2,10);
printf("%2d: %16s %16s\n",k,s1,s2);
}
printf("\n\n");
}
while(getchar());
return 0;
}