#include <iostream>
#include <cstring>

using namespace std;

//!!! P.S. Некоторые проверки в программе не выполняются, для упрощения восприятия

/**
 * @brief Генерируем лягушек
 * @param frogs Указатель на массив с лягушками [m + n + 1] размерности
 * @param m T лягушек
 * @param n F лягушек
 **/
void generateFrogs(char *frogs, const int m , const int n) {
    int count = m + n + 1;
    memset(frogs, ' ', count);

    for(int i = 0; i < m; i++) {
        frogs[i] = 'T';
    }
    for(int i = m + 1; i < count; i++) {
        frogs[i] = 'F';
    }
}

/**
 * @brief Заданные шаблоны поведения лягушек возле свободной ячейки
 */
struct Patterns{
public:

    // T1 <-- Цифра - количество шагов
    // ^
    // |
    // Символ - тип лягушки
    /**
     * @brief Задаем шаблоны в конструкторе структуры и записываем указатели в m_list
     */
    Patterns() {
        m_list[0] = "TF FT"; // T2
        m_list[1] = "FT TF"; // F2

        m_list[2] = "FF FT"; // F1
        m_list[3] = "TT TF"; // F2

        m_list[4] = "FF TF"; // F2
        m_list[5] = "TT FT"; // T1

        m_list[6] = "TF FF"; // T2
        m_list[7] = "FT TT"; // T1

        m_list[8] = "FT FF"; // F1
        m_list[9] = "TF TT"; // T2

        m_list[10] = "FT FT"; // F1 or T1
        m_list[11] = "TF TF"; // lock

        m_list[12] = "TT FF"; // F1 or T1

        m_list[13] = "FF FF"; // F1;
        m_list[14] = "TT TT"; // T1;

        m_list[15] = "FF TT"; // done
    }
    /**
     * @brief Возвращает указатель на заданный шаблон.
     * Нужна лишь для итеративного поиска.
     * @param num Номер шаблона в m_list
     * @return Указатель на заданный шаблон
     */
    const char *pattern(const int &num) {
        // Проверку не стал делать, для упрощения восприятия
        return m_list[num];
    }
    /**
     * @brief Возвращает число шаблонов
     * @return Число шаблонов
     */
    int size() {
        return m_size;
    }

private:
    static const int m_size = 16;
    // Массив с указателями на массивы шаблонов
    const char *m_list[m_size];

} frog_patterns;

/**
 * @brief Получение текущего состояния (шаблона) в массиве с лягушками
 * @param currentPattern Указатель на формируемый массив для записи в него шаблона
 * @param frogs Указатель на массив с лягушками
 * @param count Размер массива с лягушками
 * @param iter Текущее положение пробела
 */
void getCurrentPattern(char *currentPattern, char *frogs, const int &count, const int &iter) {
    //Задаем шаблон текущего положения для последующего сравнения с заданными шаблонами
    memcpy(currentPattern, &frogs[iter - 2], 5); // dangerous !!! Опасно, выходим за рамки заданного массива. Но работает

    // Задаем МНИМЫХ лягушек в текущий шаблон для последующего сравнения с заданными шаблонами.
    // Когда символ пробела находится с краю, например: 'FF |' или '|T FF'  (где | край массива)
    // То приходим в несколько неодназначную ситуацию.
    // Проще всего этого избежать добавив МНИМЫХ лягушек в шаблон для сравнения.
    // Для конечных точек характеры следующие МНИМЫЕ лягушки:   Для начального положения(крайнего левого предела) характерна мнимая F
    //                                                          Для последнего положения(крайнего правого предела) характерна мнимая T
    // P.S. МНИМЫЕ лягушки на то и мнимые, они ни как не дополняют исходный массив, они лишь заполняют шаблон для сравнения.

    if(iter == 0) {
        currentPattern[0] = 'F';
        currentPattern[1] = 'F';
    }
    if(iter == 1) {
        currentPattern[0] = 'F';
    }
    if(iter == (count - 1)) {
        currentPattern[3] = 'T';
        currentPattern[4] = 'T';
    }
    if(iter == (count - 2)) {
        currentPattern[4] = 'T';
    }
}

/**
 * @brief Перемещение лягушки на место пустой ячейки
 * @param frogs Указатель на массив с лягушками
 * @param iter Текущее положение пробела
 * @param type Тип лягушки
 * @param step Шаг для перемещения лягушки
 */
void moveFrog(char *frogs, const int &iter, const char &type, const int &step) {
    if(type == 'F') {
        frogs[iter] = frogs[iter + step];
        frogs[iter + step] = ' ';
    }
    if(type == 'T') {
        frogs[iter] = frogs[iter - step];
        frogs[iter - step] = ' ';
    }
}

/**
 * @brief Основной цикл сравнения состояний
 * @param frogs Указатель на массив с лягушками
 * @param m T лягушек
 * @param n F лягушек
 * @param iter Текущее положение пробела
 * @return Возвращает 1, если перемещение всех лягушек завершено. В остальных случаях 0.
 */
int move(char *frogs, const int &m , const int &n, const int &iter) {
    int count = m + n + 1;

    char currentPattern[5];
    memset(currentPattern, ' ', 5);
    getCurrentPattern(currentPattern, frogs, count, iter);

    // Проходим по всем заданным шаблонам
    for(int i = 0; i < frog_patterns.size(); i++) {
        // Сравниваем
        int rescmp = memcmp(currentPattern, frog_patterns.pattern(i), 5);
        if(rescmp == 0) {
            // При совпадении перемещаем
            switch (i) {
            case 0:
                moveFrog(frogs, iter, 'T', 2); // T2
                break;
            case 1:
                moveFrog(frogs, iter, 'F', 2); // F2
                break;
            case 2:
                moveFrog(frogs, iter, 'F', 1); // F1
                break;
            case 3:
                moveFrog(frogs, iter, 'F', 2); // F2
                break;
            case 4:
                moveFrog(frogs, iter, 'F', 2); // F2
                break;
            case 5:
                moveFrog(frogs, iter, 'T', 1); // T1
                break;
            case 6:
                moveFrog(frogs, iter, 'T', 2); // T2
                break;
            case 7:
                moveFrog(frogs, iter, 'T', 1); // T1
                break;
            case 8:
                moveFrog(frogs, iter, 'F', 1); // F1
                break;
            case 9:
                moveFrog(frogs, iter, 'T', 2); // T2
                break;
            case 10:
                moveFrog(frogs, iter, 'F', 1); // F1 or T1
                break;
            case 12:
                if((m % 2) == 0) {
                    moveFrog(frogs, iter, 'T', 1);
                } else {
                    moveFrog(frogs, iter, 'F', 1);
                }
                //moveFrog(frogs, iter, 'F', 1); // F1 or T1 //if m is even use T1
                break;
            case 13:
                moveFrog(frogs, iter, 'F', 1);
                break;
            case 14:
                moveFrog(frogs, iter, 'T', 1);
                break;
            case 15:
                return 1;
                break;
            }
        }
    }
    return 0;
}

/**
 * @brief Запуск цикла алгоритма
 * @param m T лягушек
 * @param n F лягушек
 */
void jumpAlg(const int m , const int n) {
    int count = m + n + 1;
    char frogs[count + 1];      // +1 чтобы добавить символ \0 в конец, для корректного вывода через printf
    frogs[count] = '\0';        // тут и добавим
    generateFrogs(frogs, m, n); // Генерируем массив с лягушками

    int counter = 0;
    while(true) {
        printf("%s\n", frogs);
        int ret = 0;
        for(int iter = 0; iter < count; iter++) {
            // При нахождении пробела, входим в Основной цикл сравнения состояний
            if(frogs[iter] == ' ') {
                ret = move(frogs, m, n, iter);
                break;
            }
        }
        if(ret == 1) {
            printf("Count steps: %d\n", counter);
            break;
        }
        counter++;
    }
}

int main()
{
    //
    // T, F
    jumpAlg(3, 5);
    return 0;
}