Списки. Стеки. Очереди

//Квадрат разбит на 4^k равновеликих квадратных клеток. Квадрат перегибается поочередно относительно вертикальной 
//(правая половина подкладывается под левую) и горизонтальной (нижняя половина подкладывается под верхнюю) 
//оси симметрии до тех пор, пока все клетки не будут расположены друг под другом. 
//Требуется занумеровать клетки исходного квадрата таким образом, 
//чтобы в результате выполнения операций перегиба номера клеток, расположенных друг под другом, 
//образовали числовую последовательность 1,2,3,...,4 ^ k, начиная с верхней клетки.
 
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
 
struct point
{
    int value;
    int x, y;
    point (int X, int Y) : x(X), y(Y), value(0) {}
    point (int X, int Y, int val) : x(X), y(Y), value(val) {}
};
 
size_t numberOfDigits(size_t n) {
    size_t count = 0;
    while (n != 0) {
        n /= 10;
        ++count;
    }
    return count;
}
 
// горизонтальный сгиб
void horizFold(std::vector<point>** mass, size_t curlen) {
    // добавляем точки
    for (size_t i = 0; i < curlen / 2; ++i) {
        for (size_t j = 0; j < curlen; ++j) {
            std::copy(mass[curlen - i - 1][j].rbegin(), mass[curlen - i - 1][j].rend(), back_inserter(mass[i][j]));
        }
    }
    // очищаем поля
    for (size_t i = curlen / 2; i < curlen; ++i) {
        for (size_t j = 0; j < curlen; ++j) {
            mass[i][j].clear();
        }
    }
}
 
// вертикальный сгиб
void vertFold(std::vector<point>** mass, size_t curlen) {
    // добавляем точки
    for (size_t i = 0; i < curlen; ++i) {
        for (size_t j = 0; j < curlen / 2; ++j) {
            std::copy(mass[i][curlen - j - 1].rbegin(), mass[i][curlen - j - 1].rend(), back_inserter(mass[i][j]));
        }
    }
    // очищаем поля
    for (size_t i = curlen; i < curlen; ++i) {
        for (size_t j = 0; j < curlen / 2; ++j) {
            mass[i][j].clear();
        }
    }
}
 
int main()
{
    size_t k;    // степень четвёрки
    std::cout << "Enter k" << std::endl;
    std::cin >> k;
    size_t len = (size_t)pow(2.0, 1.0 * k);  // длина стороны квадрата
 
    // подсчитаем количество цифр максимального номера квадрата, для читаемого вывода
    size_t numOfDig = numberOfDigits((size_t)pow(4.0, 1.0 * k));  
 
    int** originalMass = new int*[len];  // тот массив, который мы захотим получить
    for (size_t i = 0; i < len; ++i) {
        originalMass[i] = new int[len];
    }
 
    std::vector<point>** mass = new std::vector<point>*[len];  // создадим массив векторов точек
    for (size_t i = 0; i < len; ++i) {
        mass[i] = new std::vector<point>[len];
    }
 
    for (size_t i = 0; i < len; ++i) {
        for (size_t j = 0; j < len; ++j) {
            mass[i][j] = std::vector<point>(1, point(i, j));  // и каждый элемент этого массива инициализируем вектором
        }                                                 // из одной точки, 
    }                                              // в которую сохраним координаты текущего элемента массива
 
    size_t curlen = len;   // текущая длина
 
    while (curlen != 1) {               // "сгибаем" массив до тех пор, пока он не станет одной клеткой
        vertFold(mass, curlen);
        horizFold(mass, curlen);
        curlen /= 2;
    }
 
    // после всех сгибов у нас все точки окажутся в векторе, который хранится в верхнем левом элемента массива mass[0][0]
    for (size_t i = 0; i < mass[0][0].size(); ++i) {
        // придадим значение каждой точке этого вектора в обратном порядке, т.к. начальный элемент вектора находится "внизу"
        (mass[0][0])[i].value = mass[0][0].size() - i;  
        // заполняем наш исходный массив (заполнение элементов массива идёт в порядке расположения точек в векторе)
        originalMass[(mass[0][0])[i].x][(mass[0][0])[i].y] = (mass[0][0])[i].value;
    }
 
    // выводим искомый массив и получаем пронумерованный квадрат
    for (size_t i = 0; i < len; ++i) {
        for (size_t j = 0; j < len; ++j) {
            std::cout << std::setw(numOfDig + 1) << originalMass[i][j];
        }
        std::cout << std::endl;
    }
 
    system("PAUSE>0");
    return 0;
}