Ограничение по времени: 3 секунды Ограничение по п...

Да, твою идею можно оформить именно как BFS + хранение информации о диагоналях, чтобы не проходить одну и ту же диагональ много раз.

Идея

Пишем обычный BFS по клеткам доски.

Из каждой клетки у фигуры есть два типа ходов:

1. Как конь — всего не больше 8 переходов, их можно просто перебрать.
2. Как слон — потенциально до O(n) клеток с каждой клетки. Если каждый раз полностью проходить диагонали, получится слишком медленно.

Поэтому храним дополнительную информацию о диагоналях.

Твоя идея с состояниями диагонали сводится к тому, что любую диагональ можно однозначно определить по:

• направлению диагонали;
• её положению на доске.

Вместо d[2][2][700][700] это можно записать немного проще.

Для диагонали вида \ значение

cpp
x - y

одинаково для всех клеток.

Для диагонали вида / значение

cpp
x + y

одинаково для всех клеток.

То есть достаточно двух массивов:

cpp
bool used1[2 * N]; // диагонали x - y
bool used2[2 * N]; // диагонали x + y

Это ровно та же идея: для каждого состояния диагонали запоминаем, обрабатывали мы её уже или нет.

Когда BFS впервые попадает в клетку (x, y), смотрим две диагонали через неё. Если какая-то диагональ ещё не использовалась, проходим по всем клеткам этой диагонали и добавляем непосещённые клетки в BFS с расстоянием dist[x][y] + 1.

Повторно эту диагональ рассматривать уже не нужно. Почему? Первый раз она обрабатывается из клетки с минимальным возможным расстоянием, потому что это BFS. Если позже мы придём на эту диагональ из клетки с большим или таким же расстоянием, получить лучший ответ уже невозможно.

Таким образом, каждая диагональ полностью перебирается только один раз.

Сложность получается O(n²): все клетки диагоналей суммарно будут просмотрены O(n²) раз, плюс по 8 коневых ходов из каждой клетки.

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 705;

int dista[MAXN][MAXN];

bool used1[2 * MAXN]; // x - y
bool used2[2 * MAXN]; // x + y

int dx[] = {2, 2, -2, -2, 1, 1, -1, -1};
int dy[] = {1, -1, 1, -1, 2, -2, 2, -2};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            dista[i][j] = -1;

    queue<pair<int, int>> q;

    dista[1][1] = 0;
    q.push({1, 1});

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        // -------------------------
        // Ходы коня
        // -------------------------
        for (int k = 0; k < 8; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (nx < 1 || nx > n || ny < 1 || ny > n)
                continue;

            if (dista[nx][ny] == -1) {
                dista[nx][ny] = dista[x][y] + 1;
                q.push({nx, ny});
            }
        }

        // -------------------------
        // Диагональ '\'
        // x - y = const
        // -------------------------

        int id1 = x - y + n;

        if (!used1[id1]) {
            used1[id1] = true;

            // Идём влево-вверх до начала диагонали
            int sx = x;
            int sy = y;

            int shift = min(sx - 1, sy - 1);
            sx -= shift;
            sy -= shift;

            // Теперь проходим всю диагональ
            while (sx <= n && sy <= n) {
                if (dista[sx][sy] == -1) {
                    dista[sx][sy] = dista[x][y] + 1;
                    q.push({sx, sy});
                }

                ++sx;
                ++sy;
            }
        }

        // -------------------------
        // Диагональ '/'
        // x + y = const
        // -------------------------

        int id2 = x + y;

        if (!used2[id2]) {
            used2[id2] = true;

            // Идём влево-вниз / вверх-вправо
            // до одного из концов диагонали
            int sx = x;
            int sy = y;

            int shift = min(sx - 1, n - sy);
            sx -= shift;
            sy += shift;

            // Проходим всю диагональ
            while (sx <= n && sy >= 1) {
                if (dista[sx][sy] == -1) {
                    dista[sx][sy] = dista[x][y] + 1;
                    q.push({sx, sy});
                }

                ++sx;
                --sy;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cout << dista[i][j];
            if (j != n)
                cout << ' ';
        }
        cout << '\n';
    }

    return 0;
}

То есть основная мысль именно твоя: BFS, но кроме расстояний по клеткам храним состояние диагоналей, чтобы одна и та же диагональ не раскрывалась повторно. Твои состояния «какая диагональ и откуда она начинается» здесь просто заменены на более удобные идентификаторы x-y и x+y.