1:      1,     1
 2:      2,     1
 3:      6,     2
 4:     19,     5
 5:     63,    12
 6:    216,    35
 7:    760,   108
 8:   2725,   369
 9:   9910,  1285
10:  36446,  4655
11: 135268, 17073

***
* *
***

ххх
х х
хх

RS>***
RS>* *
RS>***
RS>

N=20: 2870671950

// 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 20

//4 возможных направления движения
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

char board[N+1][2*N-2];
// полимино в раскодированном виде, удобном для отражений
//поле битвы и результат работы основной функции Decode()
//матрица [y][x], в ячейках одно из 3-х значений:
//-1 - запрет - точно нет заполненной клетки
// 1 - стоит - точно есть заполненная клетки
// 0 - туман - пока неизвестно, есть ли клетка

int x1,x2,y1,y2; //границы полимино, лежащего в board[][]

//основная функция
//декодирует в board последовательность
//лежащую в массиве pack[n]
//останавливается в конце массива
//или при невозможности двигаться дальше
//в последнем случае возвращает false
//верхняя строка в результирующем board пустая
//вторая сверху строка начинается с клетки N-2
bool Decode(int pack[],int n)
{    
    static int fifo_x[N-1];
    static int fifo_y[N-1];
    static int fifo_tail=0;
    static int fifo_head=0;

    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; 
    x1=x2=fifo_x[0];
    y1=y2=fifo_y[0];

    //основной цикл декодирования
    int pos=0,count=0;
    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)              //в тумане
            {
                if(count==pack[pos])
                {
                    board[y][x]=1;  //поставили
                
                    //поправим границы
                    if(y>y2)    y2=y;
                    else if(x<x1)    x1=x;
                    else if(x>x2)    x2=x;
                    
                    //переходим к следующему элементу pack
                    if(++pos==n)
                        return true; //если конец - уходим
                    count=0;

                    //помещаем поставленную клетку в очередь 
                    fifo_y[fifo_tail]=y;
                    fifo_x[fifo_tail]=x;
                    fifo_tail++;
                }
                else
                {
                    count++;        //считаем отказы
                    board[y][x]=-1; //помечаем отказ
                }
            }
        }

        fifo_head++; //убираем обработанную клетку из очереди
    }

    return false;
}


//возвращает true если в board находится "правильно" повёрнутая конфигурация 
//"правильность" можно задавать довольно произвольно, важно чтобы однозначно - 
//среди всех 8 отражений должно быть ровно 1 правильное
bool IsMainBoard()
{
    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; 
}


//подсчитывает все полимино порядка n
void Enum(int n, unsigned int& countAll, unsigned int& countMain)
{
    countAll=countMain=0;
    if(n<2)
    {
        if(n==1)
            countAll++,countMain++;
        return;
    }

    int* pack=new int[n-1];
    memset(pack,0,(n-1)*sizeof(int));

    while(1)
    {
        if(Decode(pack,n-1))
        {
            countAll++;          //считает все полимино
            if(IsMainBoard())    
                countMain++; //считает с точностью до отражений
            pack[n-2]++;
        }
        else
        {
            for(int i=n-2;pack[i]==0;i--)
            {
            }    
            if(i==0)
            {
                delete[] pack;  
                return;
            }
            pack[i]=0;
            pack[i-1]++;
        }
    }
}


int main(int argc, char* argv[])
{
    while(1)
    {
        char s[80];
        gets(s);

        if(s[0]=='?' || strlen(s)==0 || strlen(s)>N-1) 
        {
            if(strlen(s)>N-1 || atoi(s+1)>N)
            {
                printf("To work with such big polyminoes change \"#define N ...\" line in code.\n\n");
                continue;
            }
            if(atoi(s+1)<=0)
            {
                printf("Examples:\nEnter ?10 to count polyminos with order 10.\nEnter sequence 0102 to decode it.\n\n");
                continue;
            }
            
            //считает все полимино
            unsigned int countAll,countMain,n=atoi(s+1);
            Enum(n,countAll,countMain);
            printf("N=%u Total=%u Main=%u\n\n",n,countAll,countMain);
        }
        else
        {
            int pack[N-1];
            int n=strlen(s);
            for(int i=0;i<n;i++) //читает набитую последовательность
                pack[i]=s[i]-'0';            

            bool res1=Decode(pack,n),res2=IsMainBoard();
            printf("%s %s\n\n", res1?"OK":"Fails",res1&&res2?" Main":"");
            //говорит, можно ли её декодировать и "правильная" ли она
            
            //затем выводит саму полимино - результат декодирования
            for(int y=0;y<=y2-y1;y++)
            {
                for(int x=0;x<=x2-x1;x++)
                    printf(board[y1+y][x1+x]==1? "\1":" ");
                printf("\n");
            }

            printf("\n\n");
        }
    }

    while(getchar());
    return 0;
}

    оo 
     oо
     o
     о

     1

...........
.....1

0
............
.....12

02
............
.....12.
     .3

0200
............
.....12.
     .34
      5

............
.....12.
     .34.
      5.

02003
............
.....12.
     .34.
     .5.
      6

// 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;
}

o o    o   ooo 
ooo   ooo    o 
o o    o   ooo
       o
       o

P>o o    o   ooo 
P>ooo   ooo    o 
P>o o    o   ooo
P>       o
P>       o
P>

P>А если идеально пойду вместо всех по уникальным (ах, мечта ),

P>Хотя это, конечно, заманчиво, пойти по уникальным

oo

ooo   oo   oo
      o     o

oo
oo

ooo

MP>oo
MP>

MP>ooo   oo   oo
MP>      o     o
MP>

   ooо
    o

+--+--+
|     |
+  +  |
|  |  |
+--+--+

// PolyminoLab.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 //странная цифра, но почему нет :)

//4 возможных направления движения
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

//если не жалко времени, можно рисовать лабиринт
//либо для всех порядков либо только для старшего 
int need_draw;

char board[N+1][2*N-2];
//поле битвы и результат работы основной функции Enum()
//матрица [y][x], в ячейках битсеты 000DRUL - 
//есть ли выходы отсюда в каждом из 4-х направлений 
//  0 - клетка точно не заполнена    
// -1 - пока неизвестно, заполнена ли клетка (туман) 
inline int GetWay(int y,int x,int d)    
    {return (board[y][x]>>d) & 1;}
inline void SetWay(int y,int x,int d,int w)
    { w? board[y][x]|=1<<d:board[y][x]&=~(1<<d); }

//довесок к board - перспективы заполнения
int fifo_x[N-1]; 
int fifo_y[N-1];
int fifo_tail=0;
int fifo_head=0;

int n;//сколько клеток надо поставить (цель)
__int64 countTotal;//здесь будем считать

//распечатывает превдографикой лабиринт, лежащий в board 
//некоторая морока связана с тем, чтобы вывести "в строчку"
//параметр end нужен только для того, чтобы допечатать последнюю строчку
void DrawLab(bool end=false)
{
    static const int pseudo[16]={' ',0xb5,0xd0,0xbc,0xc6,0xcd,0xc8,0xca,
                                     0xd2,0xbb,0xba,0xb9,0xc9,0xcb,0xcc,0xce};
    static char out[N+1][80];

    if(end || strlen(out[0])+n+1>75)
        for(int y=0;y<n+1;y++)
            printf(" %s\n",out[y]),out[y][0]=0;

    if(!end)
    for(int y=1;y<n+1;y++)
    for(int x=N-2-n;x<N-2+n;x++)
    {
        char ss[2];
        sprintf(ss,"%c",pseudo[board[y][x]>0? board[y][x]:0]);
        strcat(out[y-1],ss);
    }
}

//основная рекурсивная функция, в результате её работы вглубь 
//в board последовательно перебывают ровно по одному разу (!)
//все лабиринты порядка не больше n (с отражениями)
//стартуя с того, что сейчас лежит в board+fifo
//подсчитывает число продолжений до порядка n
//в результате board+fifo остаётся без изменений (!)
void Enum()
{
    if(fifo_tail==0) //первый вход
    {
        fifo_head=0;
        countTotal=0;
        
        memset(board,-1,sizeof(board));               //заполняем всё туманом
        memset(board, 0,sizeof(board[0][0])*(3*N-4)); //заполняем начало запретами

        //занесём первую клетку в fifo
        fifo_x[fifo_tail]=N-2;
        fifo_y[fifo_tail]=1;
        board[fifo_y[fifo_tail]][fifo_x[fifo_tail]]=-2;
        fifo_tail++;

        Enum();

        fifo_tail=0;        

        if(need_draw)
            DrawLab(true); //дорисуем остатки (последнюю строку)

        return;
    }

    if(fifo_tail>fifo_head)    //последовательное распространение 
    {           //выбираем один из концов и развиваемся с него
        int y=fifo_y[fifo_head];
        int x=fifo_x[fifo_head];
        fifo_head++; 
        
        // сейчас board[y][x]==-2 - признак постановки в fifo        
        board[y][x]=0; //разогнали туман

        //из точки можно пойти или не пойти в 4 разных стороны
        //цикл по разным вариантам заполнить вот именно эту клетку
        int w[4];
        for(w[3]=0;w[3]<2;w[3]++)
        for(w[2]=0;w[2]<2;w[2]++)
        for(w[1]=0;w[1]<2;w[1]++)
        for(w[0]=0;w[0]<2;w[0]++)
        {            
            int save_fifo_tail=fifo_tail;

            for(int d=0;d<4;d++)
            {
                //выясняем, какие пути уже известны
                if(board[y+dy[d]][x+dx[d]]>-1 && //точка уже стоит
                    GetWay(y+dy[d],x+dx[d],(d+2)%4)!=w[d]) //поругались
                        break;

                SetWay(y,x,d,w[d]);
                
                if(w[d]==1 && board[y+dy[d]][x+dx[d]]==-1) //реальное распространение
                {
                    //помещаем новую клетку в очередь 
                    fifo_y[fifo_tail]=y+dy[d];
                    fifo_x[fifo_tail]=x+dx[d];
                    board[fifo_y[fifo_tail]][fifo_x[fifo_tail]]=-2;
                    if(++fifo_tail>n) //переразвивались
                        break;
                }
            }

            if(d==4)//ни с кем не поругались и не переразвивались
                Enum();

            //возвращаем как было, это очень важно
            while(save_fifo_tail<fifo_tail)
            {
                fifo_tail--;
                board[fifo_y[fifo_tail]][fifo_x[fifo_tail]]=-1;
            }
        }

        //возвращаем как было, это очень важно
        board[y][x]=-2;
        fifo_head--; 
        return;
    }


    if(fifo_tail==n)//поставлено ровно n точек и дальше ставить некуда
    {
        countTotal++;

        //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        //вот именно в этом месте мы побываем ровно столько раз, 
        //сколько есть уникальных лабиринтов площади n (с отражениями)
        //в этот момент в board лежит очередной уникальный лабиринт
        //если элемент (байт) равен 0 или -1, то клетка не входит в лабиринт
        //если имеет вид 0000DRUL, то L,U,R,D==1 если в эту сторону есть выход
        //значений другого вида в board быть не может
        //в этом месте с лабиринтом можно что-то сделать, например распечатать
        //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                
        if(need_draw)
            DrawLab();
    }
}


int main()
{
    printf("\n Enter max labirint size 0<N<32 to count.\n Add '+' after N to draw labirints while counting.\n\n");
    
    while(1)
    {
        char s[80];
        printf(" N=");
        gets(s);
        n=atoi(s);
        if(n<1 || n>31)
        {
            printf(" Labirint size must be 0<N<32.\n\n");
            continue;
        }
        if(n>10 && s[strlen(s)-1]=='+')
        {
            printf(" Too many labirints to draw!\n");
            need_draw=0;
        }
        else
        {
            need_draw = (s[strlen(s)-1]=='+');
        }
        printf("\n");

        Enum();
        
        printf("\n");
        _i64toa(countTotal,s,10);
        printf(s);
        printf("\n\n");
    }

    return 0;
}

// Основана на проге Пушкина от 11.03.03 11:37.
// Hail Pushkin!

#include <iostream>
#include <cassert>
#include <windows.h>

using namespace std;
// Ansifixion :)
#define for if(false); else for

// Ну это как-бы максимальное количество клеток лабиринта.
#define N 20

typedef unsigned short cell_type;

// Поле. Размер больше чем у Пушкина, так как мне пришлось еще санитарную 
// зону сделать.
cell_type field[N+2][2*N];

#define L_MASK    0x03
#define L_PASS    0x00
#define L_WALL    0x01
#define L_UNK     0x02

#define U_MASK    0x0C
#define U_PASS    0x00
#define U_WALL    0x04
#define U_UNK     0x08

#define R_MASK    0x30
#define R_PASS    0x00
#define R_WALL    0x10
#define R_UNK     0x20

#define D_MASK    0xC0
#define D_PASS    0x00
#define D_WALL    0x40
#define D_UNK     0x80

#define OCCUPIED    0x0100
#define DENIED      0x0200

cell_type dir_mask[4]={L_MASK, U_MASK, R_MASK, D_MASK};
cell_type dir_pass[4]={L_PASS, U_PASS, R_PASS, D_PASS};
cell_type dir_wall[4]={L_WALL, U_WALL, R_WALL, D_WALL};
cell_type dir_unk[4]={L_UNK, U_UNK, R_UNK, D_UNK};

int dx[4]={-1, 0, +1, 0};
int dy[4]={0, -1, 0, +1};
//int opp[4]={2, 3, 0, 1};
#define opp(d) ((d)^2)

int xmin, xmax, ymin, ymax;

#if !defined(NOBREAK)

// Эта штука нужна, чтобы можно было прервать нумерацию лабиринтов при помощи 
// Ctrl-Break или Ctrl-C, а сама прога осталась жива.
class BreakHandler
{
public:
    BreakHandler()
    {
        _stopflag=false;
        ::SetConsoleCtrlHandler(HandlerRoutine, TRUE);
    }
    ~BreakHandler()
    {
        ::SetConsoleCtrlHandler(HandlerRoutine, FALSE);
    }

    bool IsBreak()
    {
        if(!_stopflag)
            return false;
        _stopflag=false;
        return true;
    }
private:
    static BOOL WINAPI HandlerRoutine(DWORD dwCtrlType)
    {
        switch(dwCtrlType)
        {
        case CTRL_C_EVENT:
        case CTRL_BREAK_EVENT:
            _stopflag=true;
            break;
        default:
            return FALSE;
        }
        return TRUE;
    }
private:
    volatile static bool _stopflag;
};

volatile bool BreakHandler::_stopflag=false;

#endif // !defined(NOBREAK)

// Декодирует строку. Возвращает:
// 0 - строка нормально декодирована, лабиринт закрыт.
// 1 - строка не может быть декодирована - элемент последовательности принимает
//     слишком большое значение, или заперлись.
// 2 - строка декодирована, но лабиринт не закрыт.
// size - количество клеток лабиринта. Длина кодирующей последовательности 
// должна быть равна size.
int Decode(int *code, int size)
{
    int fifo_x[N];
    int fifo_y[N];
    int fifo_tail=0;
    int fifo_head=0;

    for(int y=0; y<N+2; ++y)
        for(int x=0; x<2*N; ++x)
            field[y][x]=L_UNK|U_UNK|R_UNK|D_UNK;
    for(int x=0; x<2*N; field[0][x++]|=DENIED);
    for(int x=0; x<N-1; field[1][x++]|=DENIED);

    int x=N-1;
    int y=1;
    
    xmin=xmax=x;
    ymin=ymax=y;

    for(;;)
    {
        // Занимаем клетку.
        field[y][x]|=OCCUPIED;

        // отгораживаемся от запрещенных клеток.
        for(int d=0; d<4; ++d)
            if((field[y+dy[d]][x+dx[d]]&DENIED)!=0 &&
               (field[y][x]&dir_mask[d])==dir_unk[d])
                field[y][x]^=dir_unk[d]^dir_wall[d];

        //*/ Ставим стенки согласно символу кодовой последовательности.
        int wallflags=*code;
        for(int d=0; d<4; ++d)
            if((field[y][x]&dir_mask[d])==dir_unk[d])
            {
                field[y][x]^=dir_unk[d];
                field[y][x]^=(wallflags&1)?dir_wall[d]:dir_pass[d];
                field[y+dy[d]][x+dx[d]]^=dir_unk[opp(d)];
                field[y+dy[d]][x+dx[d]]^=(wallflags&1)?dir_wall[opp(d)]:dir_pass[opp(d)];
                wallflags>>=1;
            }
        if(wallflags!=0)
            return 1;
        /**/

        // Добавляем данную клетку в начало очереди.
        fifo_x[fifo_head]=x;
        fifo_y[fifo_head]=y;
        ++fifo_head;

        // не пора ли сваливать?
        ++code;
        if(--size==0)
            break;

        while(fifo_head>fifo_tail)
        {
            // Это как бы "break 2;"
            bool bBreak=false;
            
            register int tail_x=fifo_x[fifo_tail];
            register int tail_y=fifo_y[fifo_tail];
            for(int d=0; d<4; ++d)
                if((field[tail_y][tail_x]&dir_mask[d])==dir_pass[d] &&
                   (field[tail_y+dy[d]][tail_x+dx[d]]&OCCUPIED)==0)
                {
                    x=tail_x+dx[d];
                    y=tail_y+dy[d];
                    
                    // break 2;
                    bBreak=true;
                    break;
                }

            if(bBreak)
                break;

            ++fifo_tail;
        }

        // Заперлись (кодовая последовательность не исчерпана, а очередь клеток
        // для развития опустошена).
        if(fifo_head==fifo_tail)
            return 1;

        // Подправим границы.
        if(x<xmin)      xmin=x;
        else if(x>xmax) xmax=x;

        if(y<ymin)      ymin=y;
        else if(y>ymax) ymax=y;
    }

    // Проверим, закрыт ли лабиринт. Воспользуемся тем, что к настоящему моменту
    // координаты всех клеток находятся в очереди.
    for(int i=0; i<fifo_head; ++i)
    {
        register int x=fifo_x[i];
        register int y=fifo_y[i];
        for(int d=0; d<4; ++d)
            if((field[y][x]&dir_mask[d])==dir_pass[d] &&
               (field[y+dy[d]][x+dx[d]]&OCCUPIED)==0)
                return 2;
    }

    return 0;
}

void Print()
{
    for(int y=ymin; y<=ymax; ++y)
    {
        for(int x=xmin; x<=xmax; ++x)
        {
            if((field[y][x]&U_MASK)==U_WALL) cout<<"+--";
            else                             cout<<"+  ";
        }
        cout<<'+'<<endl;
        for(int x=xmin; x<=xmax; ++x)
        {
            if((field[y][x]&L_MASK)==L_WALL) cout<<'|';
            else                             cout<<' ';
            if((field[y][x]&OCCUPIED)!=0) cout<<"\xDB\xDB";
            else                          cout<<"  ";
        }
        if((field[y][xmax]&R_MASK)==R_WALL) cout<<'|';
        cout<<endl;
    }
    for(int x=xmin; x<=xmax; ++x)
    {
        if((field[ymax][x]&D_MASK)==D_WALL) cout<<"+--";
        else                                cout<<"+  ";
    }
    cout<<'+'<<endl;
}

void Enum(int n, int verbose)
{
    if(n>N)
    {
        cout<<"Code sequence is too long"<<endl;
        return;
    }
    if(n==0)
        return;

#if !defined(NOBREAK)
    BreakHandler bh;
#endif // !defined(NOBREAK)

    int *pack=new int[n];
    memset(pack, 0, n*sizeof(int));

    int count=0;

    for(;;)
    {

#if !defined(NOBREAK)
        if(bh.IsBreak())
        {
            delete[] pack;
            cerr<<"^C"<<endl;
            return;
        }
#endif // !defined(NOBREAK)

        int res=Decode(pack, n);
        if(res==2)
        {
            ++(pack[n-1]);
        }
        else if(res==0)
        {
            if(verbose>0)
            {
                for(int i=0; i<n; cout<<pack[i++]);
                cout<<endl;
            }
            if(verbose>1)
            {
                Print();
                cout<<endl;
            }
            ++count;
            ++(pack[n-1]);
        }
        else if(res==1)
        {
            int i;
            for(i=n-1; pack[i]==0; --i) continue;
            if(i==0)
            {
                delete[] pack;
                cout<<"Mazes counted: "<<count<<endl<<endl;
                return;
            }
            pack[i]=0;
            ++(pack[i-1]);
        }
    }
}

int main()
{
    for(;;)
    {
        cerr<<'>';

        string str;
        getline(cin, str);

        if(str=="quit" || str=="exit")
            break;
        else if(str=="?" || str=="help")
        {
            cout<<
                "quit or exit - quit the program\n"
                "\? or help    - show this help message\n"
                "\?<n>         - show number of mazes composed of n cells\n"
                "\?\?<n>        - show number of mazes composed of n cells and code sequence\n"
                "               of each maze\n"
                "\?\?\?<n>       - show number of mazes composed of n cells and code sequence\n"
                "               and picture of each maze\n"
                "<ccccc>      - decode code sequence and show maze picture\n"
                "\n";
        }
        else if(str[0]=='?')
        {
            int verbose=-1;
            string::iterator itr;
            for(itr=str.begin(); itr!=str.end() && *itr=='?'; ++itr, ++verbose);
            
            Enum(atoi(string(itr, str.end()).c_str()), verbose);
        }
        else
        {
            if(str.length()>N)
                cout<<"Code sequence is too long"<<endl;
            else
            {
                int *pack=new int[str.length()];

                string::const_iterator itr;
                int pos;
                for(itr=str.begin(), pos=0; itr!=str.end(); ++itr, ++pos)
                    pack[pos]=(*itr)-'0';

                switch(Decode(pack, str.length()))
                {
                case 0:
                    Print();
                    cout<<endl;
                    break;
                case 1:
                    cout<<"Invalid code sequence"<<endl;
                    break;
                case 2:
                    cout<<"Maze is not closed"<<endl;
                    Print();
                    cout<<endl;
                    break;
                }

                delete[] pack;
            }
        }
    }

    return 0;
}

Сколько стенок можно поставить в кваднате NxN так, чтобы он остался односвязным?

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