А конь по кругу ходит?

Question

[impelix]

снова я со своими конями.
На этот раз переписал алгоритм для одного коня.

#include <iostream>
#include <set>
#include <queue>
#include <climits>
using namespace std;

int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };

bool isValid(int x, int y, int N) {
    return (x >= 0 && x < N) && (y >= 0 && y < N);
}

int bfs(int N, int x,int y, int x1, int y1)
{
    set<pair<int, int>> visited;
    queue<pair<int, int>> q;\
    pair <int, int> temp;
    temp = make_pair(x, y);
    q.push(temp);
    while (!q.empty()) {
        pair<int, int> node = q.front();
        q.pop();
        int dist = 0;
        if (x == x1 && y == y1) {
            return dist;
        }
        if (!visited.count(node)) {
            visited.insert(node);
            for (int i = 0; i < 8; i++) {
                int x1 = x + row[i];
                int y1 = y + col[i];
                if (isValid(x1, y1, N)) {
                    q.push(make_pair(x1, y1));
                }
            }
        }
    }
    return INT_MAX;
}

int main()
{
    int N;
    cin >> N;
    N++;
    int x, y, x1, y1;
    cin >> x >> y;
    cin >> x1 >> y1;
    cout << bfs(N, x, y, x1, y1);
    return 0;
}

Суть в том что конь должен добраться до конкретной клетки. И вывести надо количество ходов. N здесь размер поля. Но ответ какой то нереально большой. Снова обращаюсь к вам

Comments

[Армянское Радио]

https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...

[mayton2019]

На больших расстояниях я рассматривал коня как корабль который может плыть по 8 азимутам. 30 градусов. 60. 120. 150 и так далее. Тут - как-бы ни у кого вопросов не возникает. Конь-корабль. Плывет быстро. Но грубо. Может промахнуться. Как быть чтобы не промахнуться.

Далее.

Для близких я рисовал матрицу дистанций в ходах. Для 1 коня получается 5х5. Вот типа такого.

4 1 2 1 4
1 2 3 2 1
2 3 0 3 2
1 2 3 2 1
4 1 2 1 4

Вот. Если конь стоит в центре матрицы то расстояние от него до самого себя - 0 шагов. И так далее.

Теперь грубый алгоритм коня-корабля можно совместить с точной подгонкой коня под конкретную координату.
Этот точный алгоритм можно решать через BFS с ограничением в глубину 4 хода.

UPD:

Короче мой поинт в том чтобы не мучать BFS а просто использовать 2 алгоритма последовательно. Надеюсь автор меня услышит.

[kalapanga]

Количество ходов здесь в принципе не может быть выведено, т.к. его никто и не считает. Функция bfs может вернуть либо 0 либо INT_MAX. Как минимум для начала надо это поправить.

[Akina]

Из текущего местоположения проводим прямую, максимально близко проходящую от точки назначения.
Из точки назначения проводим прямую, максимально близко проходящую к текущему местоположению и пересекающую первую.
В области их пересечения всегда существует быстрый переход с одной прямой на другую за 1 ход.
ЕМНИП алгоритм применим, если координаты различаются больше чем на +/- 3.

[impelix]

Да да я опять со своими конями

Answer 1

[Wataru]

Что-то не то с bfs. Вместо set visited надо иметь двумерный массив, в котором надо считать расстояния. Значение оттуда же и возвращать. Еще плохой код в том что локальные x1, y1 имеют те же имена, что и аргументы функции.

Comments

[impelix]

#include <iostream>
#include <map>
#include <queue>
#include <climits>
using namespace std;
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };
int n;
vector<int> xcor;
vector<int> ycor;
bool valid(int x, int y)
{
    return (x < 0 || y < 0 || x >= n || y >= n);
}


struct Node
{
    int x, y, dist;
    Node(int x, int y, int dist = 0) : x(x), y(y), dist(dist) {}
    bool operator<(const Node& o) const
    {
        return x < o.x || (x == o.x && y < o.y);
    }
};
int BFS(Node st, Node nd)
{
    map<Node, bool> visited;
    queue<Node> q;
    q.push(st);
    while (!q.empty())
    {
        Node node = q.front();
        q.pop();
        int x = node.x;
        int y = node.y;
        int dist = node.dist;
        if (x == nd.x && y == nd.y)
            return dist;
        if (!visited.count(node))
        {
            visited[node] = false;
            for (int i = 0; i < 8; ++i)
            {
                int x1 = x;
                if (row[i] < 0 ? x > abs(row[i]) : x < INT_MAX - row[i])
                    x1 += row[i];

                int y1 = y;
                if (col[i] < 0 ? y > abs(col[i]) : y < INT_MAX - col[i])
                    y1 += col[i];

                if (x1 != x && y1 != y) {
                    q.push({x1, y1, dist + 1});
                }
            }
        }
    }
    return INT_MAX;
}


int main()
{
    int x, y, x1, y1;
    cin >> n >> x >> y >> x1 >> y1;
    Node start = { x, y };
    Node end = { x1, y1 };
    cout<<BFS(start, end);
    for(int i = 0; i < xcor.size(); ++i)
        cout << xcor[i] << ' ' << ycor[i] << endl;
    return 0;
}

Смог посчитать ходы, но оказывается надо еще сделать штуку которая выводит последовательность, тут я реально в ступор впал. Вроде бы пытался пушбекать в разных местах x и y в вектора xcor и ycor. но не помогло особо

[Wataru]

impelix, не совсем поавильно. Надо чтобы dist хранился в map, а не был частью ключа. Вместо проверки на visited, можно смотреть, что по заданным координатам в map что-то лежит. Если нет - положить туда +1 к тому, что лежит по координатам из очереди.

[Alexandroppolus]

impelix,

но оказывается надо еще сделать штуку которая выводит последовательность

какую последовательность? маршрут коня?
тогда кроме dist сохраняй в ячейке двумерного массива (о котором сказал Wataru ) ещё и координаты предыдущей ячейки, откуда пришел. Ну или не координаты, а направление на неё. Потом по этим переходам восстановишь путь. Но смутно припоминаю, что задача была лишь о длине пути..

[impelix]

Alexandroppolus, криво написанные задачи, в таблице где показаны тестовые данные оказывается есть пояснение что нужен еще сам маршрут

[impelix]

Wataru, но вроде дист у меня хранится в visited только я так понимаю вы предлагает хранить предка еще там и идти потом по предкам?

[Wataru]

impelix, вы dist храните в КЛЮЧЕ мапа. Вы dist игнорируете в операторе сравнения и две ошибки какбы компенсируют друг друга, но это концептуально - бред. Вам надо мап из координат в int- расстояние и пару координат.