1, C++ (vc++) - rextester

Language: Layout:

#include <vector>
#include <iostream>
#include <iomanip>
#include <queue>
#include <stack>
#include <set>
 
using namespace std;
 
struct Node
{
    Node(int i, int p = -1):idx(i),prev(p){}
    int idx;   // Индекс
    int prev;  // Предыдущий узел - для восстановления пути
    bool operator <(const Node& n) const { return idx < n.idx; }
};
 
int main()
{
    
int n, k, start1, start2, finish1, finish2;
cin >> start1>> start2 >>finish1 >> finish2;
    k=0;
    n=8;
int start, finish;
    start = (start1-1)+(n*(start2-1));
    finish = (finish1-1)+(n*(finish2-1)) ;   
 
    queue<Node> Q;   // Очередь BFS
    set<Node> S;     // Множество уже обработанных узлов
 
    Q.push(Node(start));
    while(!Q.empty())
    {
        S.insert(Q.front());        // Внесли в обработанные
        int index = Q.front().idx;  // Индекс
        if (index == finish) break;   // Найден!
        Q.pop();                    // Убираем из очереди
        vector<int> next;           // Возможные варианты
        if (index%n != 0) next.push_back(index - 1); //Лево
        if ((index+1)%n != 0) next.push_back(index + 1); //Право
        if (index-n >= n) next.push_back(index - n); //Верх
        if (index+n <= n) next.push_back(index + n); //Низ
        if ((index+n <= n) && ((index+1)%n != 0)) next.push_back(index + 1 + n); //Низ-право
        if ((index%n != 0) && (index+n <= n)) next.push_back(index + n - 1); //Низ-лево
        if ((index-n >= n) && ((index+1)%n != 0)) next.push_back(index - n + 1); //Верх-право
        if ((index-n >= n) && (index%n != 0)) next.push_back(index - n - 1); //Верх-лево  
        for(int i: next)            // Обработка возможных вариантов
        {
            Node n(i,index);
            if (S.find(n) != S.end()) continue;  // Уже отработан
            Q.push(n);              // Внесение в очередь еще не рассмотренных
        }
    }
 
    // Вывод цепочки - так как в обратном порядке, используем стек
    stack<int> path;
    for(int index = Q.front().idx; index != -1; )
    {
        path.push(index);
        auto i = S.find(Node(index));    // Поиск предыдущего
        if (i == S.end()) break;         // Береженого Бог бережет :)
        index = i->prev;                 // Предыдущий в цепочке
    }
    // Вывод из стека
    while(!path.empty())
    {
k=k+1;
   //     cout << path.top() << "  ";
        path.pop();
    }
    cout << k-1;
}

Show compiler warnings [ + ] Compiler args [ - ] Show input
Compilation time: 2,08 sec, absolute running time: 0,33 sec, absolute service time: 2,42 sec