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

struct stack
{
    int elem[NMAX];
    int top;
};

void init(struct stack *stk) {
    stk->top = 0;
}
void func(int num_start, int num_end, int minway, int a[N][N], int b[N], struct stack *stk)
{
    int i, j, way = 1, check = 0, del;
    i = num_start;
    while (i)
    {
        if (b[i] == way - 1)
        {
            check = 0;
            way = way - 1;

        }
        for (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);
    }
    return;
}
void func_print_way(int b[64], struct stact *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;

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

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

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

int gettop(struct stack *stk)
{
    return(stk->top);
}
int search_minway(int a[64][64], int number_start, int number_end) {

    int t, r, k, n, i, j, c[64][64];
    n = 64; // Число Вершин

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

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            c[i][j] = a[i][j]; // Построили матрицу в 1 степени, равную исходной
        }
    }

    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                r = 16000;
                for (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()
{
    struct stack *stk;
    int elem;
    int top;
    int A[64][64], i, j, y1, y2, x1, x2, num_start, num_end, b[64], minway;
    char word1, word2;
    for (i = 0; i < 64; i++)
        b[i] = 0;
    init(stk);

    for (i = 0; i < 64; i++)
    {
        for (j = 0; j < 64; j++)
            A[i][j] = 0;
    }


    for (i = 0; i < 64; i++)
    {
        for (j = 0; j < 64; 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;
        }
    }

    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[64][64], num_start, num_end);
    func(num_start, num_end, minway, A[N][N], b[N], stk);
    return;
}