@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 здесь размер поля. Но ответ какой то нереально большой. Снова обращаюсь к вам
  • Вопрос задан
  • 158 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Что-то не то с bfs. Вместо set visited надо иметь двумерный массив, в котором надо считать расстояния. Значение оттуда же и возвращать. Еще плохой код в том что локальные x1, y1 имеют те же имена, что и аргументы функции.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы