Шахматный конь

@Programist_r · Регистрация: 05.04.2019

Студворк — интернет-сервис помощи студентам

Добрый день
Нужно поправить код, но не знаю как.

Такая задача:
Одно движение шахматного прыгуна (лошади) - это прыжок на два поля вертикально или горизонтально, а затем на один квадрат под прямым углом. Такое движение создает букву «Л». Все поля, доступные одним движением перемычки, отмечены крестиком на диаграмме ниже.
Рассмотрим неограниченную шахматную доску, на которой стоит несколько перемычек и на которой выделено одинаковое количество целевых полей. После выполнения определенного количества ходов (описанных выше) перемычки должны находиться на целевых полях. Как это сделать, выполнив минимальное количество ходов? Задача Напишите программу, которая для заданного распределения выходных N перемычек и N целевых полей найдет минимальное количество ходов, после которого перемычки окажутся на целевых полях.
Входные данные В первой строке стандартного ввода содержится целое число D (1 ≤D ≤ 20), обозначающее количество наборов данных, размещенных в следующих строках. Каждый набор состоит из строки, содержащей количество N перемычек (1≤N≤ 1000), и из следующих 2N строк, содержащих координаты выходных полей перемычек (N строк), а затем расположение целевых полей (следующие N строк). Каждая из 2N строк, содержащих координаты поля (выходной или целевой), содержит две, разделенные одним пробелом целые числа x, y (-2000000000≤x, y ≤ 2 000 000 000), обозначающие номера столбца и строки, соответственно, на пересечении какого поля. Выходные данные Стандартный выходной файл должен содержать D задач для последующих наборов данных. Каждое решение должно быть записано в одну строку, в которой должно быть одно положительное целое число K - обозначающее минимальное количество движений, необходимое для перемещения всех перемычек из начальной позиции в целевую позицию.

//4
//1
//5 5
//5 6
//2
//0 0
//1 0
//0 1
//1 1
//13
//4 1
//4 2
//3 3
//0 7
//4 3
//6 1
//3 5
//6 3
//5 4
//2 7
//3 7
//5 6
//7 5
//1 1
//3 0
//4 0
//1 4
//3 2
//0 7
//3 5
//7 3
//6 6
//7 5
//5 7
//7 6
//6 7
//15
//0 0
//0 1
//1 1
//2 0
//0 3
//3 3
//5 2
//7 0
//1 7
//3 6
//6 4
//7 4
//7 5
//6 7
//7 7
//1 1
//0 3
//4 0
//3 2
//2 3
//6 1
//0 7
//1 6
//3 5
//5 3
//4 4
//7 3
//4 7
//5 7
//7 7
правильный ответ:
//3
//4
//18
//24

Полазил по Гуглу, по изучал информацию и получилось сделать только для стандартной доски 8х8(решил начать с простого и дойти со временем до решения).

У меня не получается сделать неограниченную шахматную доску.
А как сделать это что-то не придумаю?

Если можете помочь, был бы очень благодарен вам)

Вот мой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include "pch.h"
#include <iostream>
#include <map>
#include <queue>
#include <climits>
using namespace std;
 
#define N 8
 
//8 возможных движений для коня
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };
 
// Проверяем, верны ли (x, y) координаты шахматной доски
bool valid(int x, int y)
{
    if (x < 0 || y < 0 || x >= N || y >= N)
        return false;
 
    return true;
}
 
 
struct Node
{
    // (x, y) представляет координаты шахматной доски
    //dist представляет минимальное расстояние от источника
    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 src, Node dest)
{
    // карта, чтобы проверить, посещалась ли ячейка матрицы раньше или нет
    map<Node, bool> visited;
 
    // создаем очередь, и ставим в первый узел
    queue<Node> q;
    q.push(src);
 
    // запускать до тех пор, пока очередь не станет пустой
    while (!q.empty())
    {
        // извлекаем передний узел из очереди и обрабатываем его
        Node node = q.front();
        q.pop();
 
        int x = node.x;
        int y = node.y;
        int dist = node.dist;
 
        // если пункт назначения достигнут, вернуть расстояние
        if (x == dest.x && y == dest.y)
            return dist;
 
        // Пропустить, если местоположение посещалось раньше
        if (!visited.count(node))
        {
            // пометить текущий узел как посещенный
            visited[node] = true;
 
            // проверяем все 8 возможных движений коня
            // и ставим каждое правильное движение в очередь
            for (int i = 0; i < 8; ++i)
            {
                // Получить новую действительную позицию рыцаря из текущей
                // позиция на шахматной доске и поставить ее в очередь
                //  +1 расстоянием
                int x1 = x + row[i];
                int y1 = y + col[i];
 
                if (valid(x1, y1))
                    q.push({ x1, y1, dist + 1 });
            }
        }
    }
 
    // вернуть бесконечность, если путь не возможен
    return INT_MAX;
}
 
 
int main()
{
    // исходные координаты
    Node src = { 1, 0 };
 
    // координаты пункта назначения
    Node dest = { 1, 1 };
 
    cout<<BFS(src, dest);
 
    return 0;
}

Добавлено через 1 час 45 минут
Ну очееень нужно)))

@oleg-m1973 · 27.05.2019, 21:33

Сообщение от Programist_r

У меня не получается сделать неограниченную шахматную доску.

Просто убери макрос N и передавай этот n параметром в bool valid(int x, int y, const int n) и BFS()

Добавлено через 8 минут

Сообщение от Programist_r

int x1 = x + row[i];
* * * * * * * * int y1 = y + col[i];

Здесь надо проверять перед сложением - if (row[i] < 0? x > abs(row[i]): x < std::numeric_limits<int>::max - row[i]) x1 = x + row[i];
valid() не нужно

@Programist_r · 27.05.2019, 21:36 **[ТС]**

C++
1
2
if (valid(x1, y1,))
q.push({ x1, y1, dist + 1 });

Исправил, но тогда появляется здесь ошибка(что нужно задать значения)
Какое и где?
Если это должна быть неограниченная доска(по - и по +)

Добавлено через 1 минуту
Уже увидел сообщения сверху)

@oleg-m1973 · 27.05.2019, 21:38

Сообщение от Programist_r

Исправил, но тогда появляется здесь ошибка(что нужно задать значения)
Какое и где?

А как ты до этого ошибки выдавал? Просто не меняешь позицию и всё

@Programist_r · 27.05.2019, 21:43 **[ТС]**

Чтобы <numeric_limits<int>::max - row[i]) заработал нужно добавить template< class T > class numeric_limits; ?

@oleg-m1973 · 27.05.2019, 21:46

Сообщение от Programist_r

Чтобы <numeric_limits<int>::max - row[i]) заработал нужно добавить template< class T > class numeric_limits; ?

Нет, добавь #include <limits>
https://en.cppreference.com/w/... ric_limits

@Programist_r · 27.05.2019, 21:48 **[ТС]**

Добавил
Всё равно ошибка

Добавлено через 1 минуту
После max должны быть ()

@oleg-m1973 · 27.05.2019, 21:49

Сообщение от Programist_r

Добавил
Всё равно ошибка

Поставь вместо numeric_limits<int>::max INT_MAX

Добавлено через 25 секунд
Это максимальное положительное значение для int

Добавлено через 44 секунды

Сообщение от Programist_r

После max должны быть ()

Да, поставь

@Programist_r · 27.05.2019, 21:51 **[ТС]**

Тогда ответ получается int_max

@oleg-m1973 · 27.05.2019, 21:53

Сообщение от Programist_r

Тогда ответ получается int_max

Покажи код

@Programist_r · 27.05.2019, 21:54 **[ТС]**

А как передать параметр n в BFS()?

Добавлено через 32 секунды

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include "pch.h"
#include <iostream>
#include <map>
#include <queue>
 
#include <limits>
using namespace std;
 
 
 
 
//8 возможных движений для коня
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };
 
// Проверяем, верны ли (x, y) координаты шахматной доски
bool valid(int x, int y,const int n)
{
    if (x < 0 || y < 0 || x >= n || y >= n)
        return false;
 
    return true;
}
 
 
struct Node
{
    // (x, y) представляет координаты шахматной доски
    //dist представляет минимальное расстояние от источника
    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 src, Node dest)
{
    // карта, чтобы проверить, посещалась ли ячейка матрицы раньше или нет
    map<Node, bool> visited;
 
    // создаем очередь, и ставим в первый узел
    queue<Node> q;
    q.push(src);
 
    // запускать до тех пор, пока очередь не станет пустой
    while (!q.empty())
    {
        // извлекаем передний узел из очереди и обрабатываем его
        Node node = q.front();
        q.pop();
 
        int x = node.x;
        int y = node.y;
        int dist = node.dist;
 
        // если пункт назначения достигнут, вернуть расстояние
        if (x == dest.x && y == dest.y)
            return dist;
 
        // Пропустить, если местоположение посещалось раньше
        if (!visited.count(node))
        {
            // пометить текущий узел как посещенный
            visited[node] = false;
 
            // проверяем все 8 возможных движений коня
            // и ставим каждое правильное движение в очередь
            for (int i = 0; i < 8; ++i)
            {
                if (row[i] < 0 ? x > abs(row[i]) : x < INT_MAX - row[i])
                    int x1 = x + row[i];
            }
        }
    }
 
    // вернуть бесконечность, если путь не возможен
    return INT_MAX;
}
 
 
int main()
{
    // исходные координаты
    Node src = { 5, 5 };
 
    // координаты пункта назначения
    Node dest = { 5, 6 };
 
    cout<<BFS(src, dest);
 
    return 0;
}

@oleg-m1973 · 27.05.2019, 21:59

Сообщение от Programist_r

А как передать параметр n в BFS()?

Не надо туда ничего передавать

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
           for (int i = 0; i < 8; ++i)
            {
                // Получить новую действительную позицию рыцаря из текущей
                // позиция на шахматной доске и поставить ее в очередь
                //  +1 расстоянием
                int x1 = x;
if (row[i] < 0 ? x > abs(row[i]) : x < INT_MAX - row[i])
                    x1 += row[i];
 
                int y1 = то же самое
 
                if (x1 != x || y1 != y)
                    q.push({ x1, y1, dist + 1 });
            }

@Programist_r · 27.05.2019, 22:03 **[ТС]**

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (int i = 0; i < 8; ++i)
            {
                // Получить новую действительную позицию рыцаря из текущей
                // позиция на шахматной доске и поставить ее в очередь
                //  +1 расстоянием
                int x1 = x;
                if (row[i] < 0 ? x > abs(row[i]) : x < INT_MAX - row[i])
                    x1 += x + row[i];
 
                int y1 = y;
                if (col[i] < 0 ? y > abs(col[i]) : y < INT_MAX - col[i])
                    y1 += y + col[i];
 
                    if (x1 != x || y1 != y)
                        q.push({ x1, y1, dist + 1 });
            }

Вот так?

@oleg-m1973 · 27.05.2019, 22:04

Сообщение от Programist_r

x1 += x + row[i];

x1 += row[i]
y1 += col[i]

@Programist_r · 27.05.2019, 22:15 **[ТС]**

Для второго случая ответ получается 2 , а нужно чтобы было 4.
Кони должны встать на заданные поля, но какой конь может встать на какое поле - неважно: первый на первое поле или на второе и второй на любое другое свободное, и т.д.

Расстановка для второго случая:
Код:

3! 0 0 0 0 0
2! 0 0 0 0 0
1! 0 h 0 0 0
0! 0 h 0 0 0
-1! 0 0 0 0 0
-2! 0 0 0 0 0
----------------
-1 0 2 3 4

Первый ход каждого коня:
Код:

3! 0 0 0 0 0
2! 0 0 0 1 0
1! 0 h 0 0 0
0! 0 h 0 0 0
-1! 0 0 0 1 0
-2! 0 0 0 0 0
----------------
-1 0 2 3 4

Второй ход каждого коня:
Код:

3! 0 0 0 0 0
2! 0 0 0 1 0
1! 0 h 2 0 0
0! 0 h 2 0 0
-1! 0 0 0 1 0
-2! 0 0 0 0 0
----------------
-1 0 2 3 4

Итого - 4 хода.

Вход
//2
//0 0
//1 0
//0 1
//1 1

Виход
4

Добавлено через 3 минуты
А для первого набора данных все работает прекрасно

@oleg-m1973 · 27.05.2019, 22:16

Сообщение от Programist_r

if (x1 != x || y1 != y)
* * * * * * * * * * * * q.push({ x1, y1, dist + 1 })

Сделай здесь if (x1 != x && y1 != y)

@Programist_r · 27.05.2019, 22:20 **[ТС]**

C++
1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
    // исходные координаты
    Node src = { 0, 0 };
 
    // координаты пункта назначения
    Node dest = { 0, 1 };
 
    cout<<BFS(src, dest);
 
    return 0;
}

Для этого координат вообще нету ответа

@oleg-m1973 · 27.05.2019, 22:22

Покажи код

@Programist_r · 27.05.2019, 22:23 **[ТС]**

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include "pch.h"
#include <iostream>
#include <map>
#include <queue>
 
#include <limits>
using namespace std;
 
 
 
 
//8 возможных движений для коня
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };
 
// Проверяем, верны ли (x, y) координаты шахматной доски
bool valid(int x, int y,const int n)
{
    if (x < 0 || y < 0 || x >= n || y >= n)
        return false;
 
    return true;
}
 
 
struct Node
{
    // (x, y) представляет координаты шахматной доски
    //dist представляет минимальное расстояние от источника
    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 src, Node dest)
{
    // карта, чтобы проверить, посещалась ли ячейка матрицы раньше или нет
    map<Node, bool> visited;
 
    // создаем очередь, и ставим в первый узел
    queue<Node> q;
    q.push(src);
 
    // запускать до тех пор, пока очередь не станет пустой
    while (!q.empty())
    {
        // извлекаем передний узел из очереди и обрабатываем его
        Node node = q.front();
        q.pop();
 
        int x = node.x;
        int y = node.y;
        int dist = node.dist;
 
        // если пункт назначения достигнут, вернуть расстояние
        if (x == dest.x && y == dest.y)
            return dist;
 
        // Пропустить, если местоположение посещалось раньше
        if (!visited.count(node))
        {
            // пометить текущий узел как посещенный
            visited[node] = false;
 
            // проверяем все 8 возможных движений коня
            // и ставим каждое правильное движение в очередь
            for (int i = 0; i < 8; ++i)
            {
                // Получить новую действительную позицию рыцаря из текущей
                // позиция на шахматной доске и поставить ее в очередь
                //  +1 расстоянием
                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()
{
    // исходные координаты
    Node src = { 0, 0 };
 
    // координаты пункта назначения
    Node dest = { 0, 1 };
 
    cout<<BFS(src, dest);
 
    return 0;
}

@oleg-m1973 · 27.05.2019, 22:27

Сообщение от Programist_r

// пометить текущий узел как посещенный
* * * * * * visited[node] = false;

Здесь, наверное, надо visited[node] = true

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Programist_r 1 / 1 / 0 Регистрация: 05.04.2019 Сообщений: 110
	27.05.2019, 21:43 [ТС]
	Чтобы <numeric_limits<int>::max - row[i]) заработал нужно добавить template< class T > class numeric_limits; ? 0

@Programist_r 1 / 1 / 0 Регистрация: 05.04.2019 Сообщений: 110
	27.05.2019, 21:48 [ТС]
	Добавил Всё равно ошибка Добавлено через 1 минуту После max должны быть () 0

@Programist_r 1 / 1 / 0 Регистрация: 05.04.2019 Сообщений: 110
	27.05.2019, 21:51 [ТС]
	Тогда ответ получается int_max 0

@Programist_r 1 / 1 / 0 Регистрация: 05.04.2019 Сообщений: 110
	27.05.2019, 22:15 [ТС]
	Для второго случая ответ получается 2 , а нужно чтобы было 4. Кони должны встать на заданные поля, но какой конь может встать на какое поле - неважно: первый на первое поле или на второе и второй на любое другое свободное, и т.д. Расстановка для второго случая: Код: 3! 0 0 0 0 0 2! 0 0 0 0 0 1! 0 h 0 0 0 0! 0 h 0 0 0 -1! 0 0 0 0 0 -2! 0 0 0 0 0 ---------------- -1 0 2 3 4 Первый ход каждого коня: Код: 3! 0 0 0 0 0 2! 0 0 0 1 0 1! 0 h 0 0 0 0! 0 h 0 0 0 -1! 0 0 0 1 0 -2! 0 0 0 0 0 ---------------- -1 0 2 3 4 Второй ход каждого коня: Код: 3! 0 0 0 0 0 2! 0 0 0 1 0 1! 0 h 2 0 0 0! 0 h 2 0 0 -1! 0 0 0 1 0 -2! 0 0 0 0 0 ---------------- -1 0 2 3 4 Итого - 4 хода. Вход //2 //0 0 //1 0 //0 1 //1 1 Виход 4 Добавлено через 3 минуты А для первого набора данных все работает прекрасно 0

@oleg-m1973 6772 / 4565 / 1844 Регистрация: 07.05.2019 Сообщений: 13,726
	27.05.2019, 22:22
	Покажи код 0