#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#define NMAX 100
#define N 64

typedef struct {
    int elem[NMAX];
    int top;
}Stack;

void func_print_way(int b[64], Stack *stk, int way);
char reidentity(int y);

void Stack_Init(Stack *stk) {
    stk->top = 0;
}

void push(Stack *stk, int d) {
    if (stk->top < NMAX)
        stk->elem[stk->top++] = d;
    else
        printf("Стек полон, количество элементов: %d !\n", stk->top);
}

int pop(Stack *stk) {
    if ((stk->top) > 0) {
        return(stk->elem[stk->top--]);
    }
}

int gettop(Stack *stk) {
    return(stk->top);
}

void func(int num_start, int num_end, int minway, int a[N][N], int b[N], Stack *stk) {
    int i, way = 1, check = 0, del;
    i = num_start;
    while (i) {
        if (b[i] == way - 1) {
            check = 0;
            way = way - 1;
        }
        for (int j = 0; j < 64; j++) {
            if (way != minway) {
                if (a[i][j] == 1 && b[j] == 0) {
                    push(stk, j);
                    b[j] = way;
                }
            }
            else {
                if (a[i][j] == 1 && j == num_end) {
                    check = 1;
                    func_print_way(&b[64], stk, way);
                    break;
                }
                else
                    check = -1;
            }
        }
        if (check == 1)
            break;
        if (check == -1) {
            del = pop(stk);
            i = gettop(stk);
        }
        if (check == 0)
            way++;
        i = gettop(stk);
    }
}

void func_print_way(int b[64], Stack *stk, int way) {
    int i, k, x1, y1, del;
    char word;
    k = pop(stk);
    y1 = (k % 8);
    x1 = ((int) k/8)+1;
    word = reidentity(y1);
    printf("%c %i", y1, x1);
    while (i != 0) {
        k = gettop(stk);
        if (b[k] == way - 1)
            del = pop(stk);
        else {
            way--;
            y1 = (k % 8);
            x1 = ((int)k / 8) + 1;
            word = reidentity(y1);
            printf("%c %i", y1, x1);
            del = pop(stk);
            i = way;
        }
    }
}

char reidentity(int y) {
    char word;
    switch (y) {
    case 1: word = 'A'; break;
    case 2: word = 'B'; break;
    case 3: word = 'C'; break;
    case 4: word = 'D'; break;
    case 5: word = 'E'; break;
    case 6: word = 'F'; break;
    case 7: word = 'G'; break;
    case 8: word = 'H'; break;
    }
    return word;
}

int identity(char word1) {
    int x1;
    switch (word1) {
    case 'A': x1 = 0; break;
    case 'B': x1 = 1; break;
    case 'C': x1 = 2; break;
    case 'D': x1 = 3; break;
    case 'E': x1 = 4; break;
    case 'F': x1 = 5; break;
    case 'G': x1 = 6; break;
    case 'H': x1 = 7; break;
    }
    return x1;
}

int search_minway(int a[N][N], int number_start, int number_end) {
    int r, c[N][N];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (a[i][j] == 0 && i != j) // Если не диагональ
                a[i][j] = 16000; // Во Все не заполненные пихаем бескоечность
            c[i][j] = a[i][j];
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            r = 16000;
            for (int t = 0; t < N; t++) {
                if (c[i][t] + a[t][j] < r) { // Реализация формулы
                    r = c[i][t] + a[t][j];
                }
            }
            c[i][j] = r;
        }
    }
    return c[number_start][number_end]; // Вывод длины пути из начальной точки в конечную
}

void main()
{
    Stack *stk = 0;
    int A[N][N];
    int y1, y2, x1, x2, num_start, num_end, b[64], minway;
    char word1, word2;

    for (int i = 0; i < N; i++) {
        b[i] = 0;
        stk->elem[i] = 0;
        for (int j = 0; j < N; j++)
            if ((j == i + 10) || (j == i - 10) || (j == i + 6) || (j == i - 6) || (j == i + 15) || (j == i - 15) || (j == i + 17) || (j == i - 17))
                A[i][j] = 1;
            else
                A[i][j] = 0;
    }

    Stack_Init(stk);

    printf("Введите начальную клетку \n");
    scanf_s("%c%i", &word1, &y1);
    printf("Введите конечную клетку \n");
    scanf_s("%c%i", &word2, &y2);
    x1 = identity(word1);
    x2 = identity(word2);
    num_start = y1 * 8 + x1;
    num_end = y2 * 8 + x2;
    minway = search_minway(A, num_start, num_end);
    func(num_start, num_end, minway, A, b, stk);
}