Обыграй Сфинкса: логическая головоломка о разрезании лестниц

        1 TT_FF 
2 T_TFF
3 TFT_F
4 TFTF_ 
5 TF_FT 
6 _FTFT
7 F_TFT
8 FFT_T
. FF_TT
    

        1  TTT_FFF
2  TT_TFFF
3  TTFT_FF
4  TTFTF_F
5  TTF_FTF
6  T_FTFTF
7  _TFTFTF
8  FT_TFTF
9  FTFT_TF
10 FTFTFT_
11 FTFTF_T
12 FTF_FTT
13 F_FTFTT
14 FF_TFTT
15 FFFT_TT
.  FFF_TTT
    

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