.../GNU-Linux-x86> time ./181931 
Одноклеточные:
  242   179   151   179   242 
  179   111    89   111   179 
  151    89    84    89   151 
  179   111    89   111   179 
  242   179   151   179   242 
Двухклеточные:
  608   718   622   718   608 
  718   608   508   608   718 
  622   508   424   508   622 
  718   608   508   608   718 
  608   718   622   718   608 
Общая таблица:
  850   897   773   897   850 
  897   719   597   719   897 
  773   597   508   597   773 
  897   719   597   719   897 
  850   897   773   897   850 
Всего вариантов: 3888

real    0m0.070s
user    0m0.064s
sys     0m0.000s

#include <locale>
#include <limits>
#include <iostream>
#include <iomanip>
#include <valarray>
#include <stdexcept>
#include <string>
#include <map>

using namespace std;

const bool FIGURE1[1][1] = {1};
const bool FIGURE2[1][2] = {1, 1};
const size_t BOARD_SIZE = 5;

class figure_base
{
public:
    figure_base(size_t rows, size_t cols);
    char& operator()(size_t row, size_t col);
    char operator()(size_t row, size_t col) const;
    size_t rows() const;
    size_t cols() const;
    template<class char_type, class traits_type> void out(basic_ostream<char_type, traits_type>& stream);
protected:
    typedef valarray< valarray<char> > _fields_t;
    _fields_t _fields;
    size_t _rows, _cols;
};

class figure : public figure_base
{
public:

    enum direction_t
    {
        LEFT, RIGHT
    };
    template<size_t DIM1, size_t DIM2> figure(size_t rotations, const bool (&fields)[DIM1][DIM2], char id);
    size_t rotations() const;
    char id() const;
    void rotate(direction_t direction = LEFT);
protected:
    size_t _rotations;
    char _id;
};

class board : public figure_base
{
public:
    board(size_t size);
    void place(size_t row, size_t col, const figure& fig);
    void remove(size_t row, size_t col, const figure& fig);
protected:
    bool test(size_t row, size_t col, const figure& fig) const;
};

class solver
{
public:
    typedef valarray< valarray< map<char, size_t> > > _counters_t;

    struct counters_t
    {
        _counters_t counters;
        size_t variants;
    };
    template<size_t DIM> solver(const figure(&figures)[DIM], size_t board_size);
    counters_t run();
private:
    valarray<figure> _figures;
    board _board;
    counters_t _counters;

    void place(size_t fig_no);
};

void visualisation(const char* const msg, solver::counters_t &counters, const char* const fig_ids, unsigned int divisor);
unsigned fact(unsigned val);

/*
 *
 */
int main()
{
    locale::global(locale(""));

    figure figures[3] = {figure(1, FIGURE1, '1'), figure(2, FIGURE2, '2'), figure(2, FIGURE2, '3')};

    solver::counters_t counters = solver(figures, BOARD_SIZE).run();

    unsigned div = fact(2) * fact(1);

    visualisation("Одноклеточные:", counters, "1", div);
    visualisation("Двухклеточные:", counters, "23", div);
    visualisation("Общая таблица:", counters, "123", div);
    cout << "Всего вариантов: " << counters.variants / div << endl;

    return 0;
}

void visualisation(const char* const msg, solver::counters_t &counters, const char* const fig_ids, unsigned int divisor)
{
    valarray< valarray<size_t> > result(counters.counters.size());
    for (size_t i = 0; i < result.size(); ++i)
    {
        result[i] = valarray<size_t > (static_cast<size_t> (0), counters.counters[i].size());
        for (size_t j = 0; j < result[i].size(); ++j)
        {
            const char* ids = fig_ids;
            while (*ids)
            {
                result[i][j] += counters.counters[i][j][*ids++];
            }
        }
    }
    cout << msg << endl;
    for (size_t i = 0; i < result.size(); ++i)
    {
        for (size_t j = 0; j < result[i].size(); ++j)
        {
            size_t tmp = result[i][j] / divisor;
            cout << setw(5) << tmp << ' ';
        }
        cout << endl;
    }
}

unsigned fact(unsigned val)
{
    unsigned result = 1;
    while (val)
    {
        result *= val--;
    }
    return result;
}

figure_base::figure_base(size_t DIM1, size_t DIM2)
: _fields(valarray<char>(static_cast<char> (0), DIM2), DIM1)
, _rows(DIM1)
, _cols(DIM2)
{

}

char& figure_base::operator ()(size_t row, size_t col)
{
    return _fields[row][col];
}

char figure_base::operator ()(size_t row, size_t col) const
{
    return _fields[row][col];
}

size_t figure_base::rows() const
{
    return _rows;
}

size_t figure_base::cols() const
{
    return _cols;
}

template<class char_type, class traits_type>
void figure_base::out(basic_ostream<char_type, traits_type>& stream)
{
    const ctype<char_type>& facet = use_facet< ctype<char_type> >(stream.getloc());
    static basic_string<char_type> hline(1 + 2 * _rows, facet.widen('-'));
    stream << hline << endl;
    for (size_t i = 0; i < _rows; ++i)
    {
        for (size_t j = 0; j < _cols; ++j)
        {
            stream << facet.widen('|') << (_fields[i][j] ? facet.widen(_fields[i][j]) : facet.widen(' '));
        }
        stream << facet.widen('|') << endl << hline << endl;
    }
}

template<size_t DIM1, size_t DIM2 >
figure::figure(size_t rotations, const bool (&fields)[DIM1][DIM2], char id)
: figure_base(DIM1, DIM2)
, _rotations(rotations)
, _id(id)
{
    if (_rotations > 4)
    {
        throw invalid_argument("К-во поворотов фигуры не может быть более 4х");
    }

    for (size_t i = 0; i < DIM1; ++i)
    {
        for (size_t j = 0; j < DIM2; ++j)
        {
            _fields[i][j] = fields[i][j] ? id : 0;
        }
    }
}

size_t figure::rotations() const
{
    return _rotations;
}

char figure::id() const
{
    return _id;
}

void figure::rotate(direction_t direction)
{
    figure_base newFigure(_cols, _rows);
    for (size_t i = 0; i < _cols; ++i)
    {
        for (size_t j = 0; j < _rows; ++j)
        {
            switch (direction)
            {
            case LEFT:
                newFigure(i, j) = _fields[j][ _cols - 1 - i];
                break;
            case RIGHT:
                newFigure(i, j) = _fields[_rows - 1 - j][i];
                break;
            default:
                throw invalid_argument("Неверное направление");
            }
        }
    }
    *reinterpret_cast<figure_base*> (this) = newFigure;
}

board::board(size_t size)
: figure_base(size, size)
{

}

void board::place(size_t row, size_t col, const figure& fig)
{
    if (!(row < _rows && col < _cols))
    {
        throw invalid_argument("Неверно заданы координаты");
    }
    if (!(fig.rows() <= _rows - row && fig.cols() <= _cols - col))
    {
        throw invalid_argument("Фигура слишком велика");
    }

    if (!test(row, col, fig))
    {
        throw invalid_argument("Невозможно установить");
    }

    for (size_t i = 0; i < fig.rows(); ++i)
    {
        for (size_t j = 0; j < fig.cols(); ++j)
        {
            if (!_fields[i + row][j + col] && fig(i, j))
            {
                _fields[i + row][j + col] = fig.id();
            }
        }
    }
}

void board::remove(size_t row, size_t col, const figure& fig)
{
    if (!(row < _rows && col < _cols))
    {
        throw invalid_argument("Неверно заданы координаты");
    }
    if (!(fig.rows() <= _rows - row && fig.cols() <= _cols - col))
    {
        throw invalid_argument("Фигура слишком велика");
    }

    for (size_t i = 0; i < fig.rows(); ++i)
    {
        for (size_t j = 0; j < fig.cols(); ++j)
        {
            if (fig(i, j))
            {
                _fields[i + row][j + col] = 0;
            }
        }
    }
}

bool board::test(size_t row, size_t col, const figure& fig) const
{
    for (size_t i = 0; i < fig.rows(); ++i)
    {
        for (size_t j = 0; j < fig.cols(); ++j)
        {
            if (fig(i, j))
            {
                for (size_t r = i + row - 1, er = r + 3; r != er; ++r)
                {
                    for (size_t c = j + col - 1, ec = c + 3; c != ec; ++c)
                    {
                        if (r < _rows && c < _cols && _fields[r][c])
                        {
                            return false;
                        }
                    }
                }
            }
        }
    }
    return true;
}

template<size_t DIM >
solver::solver(const figure(&figures)[DIM], size_t board_size)
: _figures(figures, DIM)
, _board(board_size)
{
}

solver::counters_t solver::run()
{
    _counters.counters = valarray< valarray< map<char, size_t> > >(valarray< map<char, size_t > >(_board.cols()), _board.rows());
    _counters.variants = 0;
    place(_figures.size());
    return _counters;
}

void solver::place(size_t fig_no)
{
    if (!fig_no)
    {
        for (size_t i = 0; i < _board.rows(); ++i)
        {
            for (size_t j = 0; j < _board.cols(); ++j)
            {
                ++_counters.counters[i][j][_board(i, j)];
            }
        }
        ++_counters.variants;
    }
    else
    {
        figure fig(_figures[--fig_no]);

        for (size_t pos = 0; pos < fig.rotations(); ++pos)
        {
            for (size_t row = 0; row < _board.rows(); ++row)
            {
                for (size_t col = 0; col < _board.cols(); ++col)
                {
                    try
                    {
                        _board.place(row, col, fig);
                        this->place(fig_no);
                        _board.remove(row, col, fig);
                    }
                    catch (...)
                    {

                    }
                }
            }
            fig.rotate();
        }
    }
}