CРОЧНО Задача С++
(p, q) - лошадь
(p, q)-лошадь - это обобщение обычного шахматного коня. (p, q)-лошадь своим ходом перемещается на p клеток в одном направлении, и на q - в другом (перпендикулярном). Например, (3, 4)-лошадь может переместиться с клетки (5, 6) на клетки (1, 3), (2, 2), (2, 10), (1, 9), (8, 10), (9, 9), (8, 2) и (9, 3). Очевидно, что обычный шахматный конь - это (2, 1)-лошадь.
Ваша задача - определить минимальное число ходов, которое требуется (p, q)-лошади, чтобы добраться от одной клетки шахматной доски M×N до другой. За пределы доски выходить запрещается.
Формат входных данных
Одна строка содержит 8 целых чисел m, n, p, q, x1, y1, x2, y2 (1 ≤ x1, x2 ≤ m ≤ 100, 1 ≤ y1, y2 ≤ n ≤ 100, 0 ≤ p ≤ 100, 0 ≤ q ≤ 100).
Формат результата
Первая строка должна содержать число ходов k, которое требуется (p, q)-лошади, чтобы добраться из клетки (x1, y1) в клетку (x2, y2). Далее должна следовать k + 1 строка, содержащая последовательные положения (p, q)-лошади на этом пути.
Если (p, q)-лошадь не может добраться из (x1, y1) в (x2, y2), выведите -1.
Примеры
Входные данные
3 3 1 1 1 1 3 3
Результат работы
2
1 1
2 2
3 3
Входные данные
2 2 1 1 1 1 1 2
Результат работы
-1
Первым шагом будет разработка алгоритма решения задачи.
1. Прочитать входные данные: значения m, n, p, q, x1, y1, x2, y2.
2. Создать функцию "minMoves", которая будет определять минимальное количество ходов и возвращать последовательные положения (p, q)-лошади на этом пути.
3. Внутри функции "minMoves" определить базовые условия:
- Если начальная и конечная клетки совпадают, вернуть 0.
- Если p и q равны 0 (невозможно совершить ход), вернуть -1.
4. Создать функцию "validMove", которая будет проверять, является ли данное положение (x, y) в пределах шахматной доски размером M×N.
5. Внутри функции "minMoves" создать очередь (queue) и добавить в нее начальную клетку (x1, y1).
6. Создать двумерный массив "visited" для отметки посещенных клеток. Изначально все элементы массива установить в false.
7. Создать двумерный массив "distance" для хранения минимального числа ходов до каждой клетки. Изначально все элементы массива установить в -1.
8. Установить для начальной клетки (x1, y1) значение 0 в массиве "distance".
9. Начать цикл по очереди, пока не будут посещены все клетки. Внутри цикла:
- Извлечь первую клетку из очереди.
- Проверить все возможные ходы для (p, q)-лошади:
- Если ход допустим (в пределах шахматной доски и клетка не посещена):
- Пометить клетку как посещенную.
- Установить новое минимальное число ходов в массиве "distance".
- Добавить новую клетку в очередь.
10. Если место назначения (x2, y2) посещено (distance[x2][y2] не равно -1), вернуть минимальное число ходов.
11. Если место назначения (x2, y2) не посещено, вернуть -1.
12. В главной программе вызвать функцию "minMoves" и вывести результат.
В результате выполнения алгоритма, программа должна вывести минимальное количество ходов (k), которое требуется (p, q)-лошади, чтобы добраться из клетки (x1, y1) в клетку (x2, y2). Затем должны быть выведены последовательные положения (p, q)-лошади на этом пути.
Пример решения задачи на языке C++:
```cpp
#include
#include
using namespace std;
// Функция проверки допустимости хода
bool validMove(int x, int y, int m, int n) {
return (x >= 1 && x <= m && y >= 1 && y <= n);
}
// Функция определения минимального числа ходов
int minMoves(int m, int n, int p, int q, int x1, int y1, int x2, int y2) {
// Базовые условия
if (x1 == x2 && y1 == y2) {
return 0;
}
if (p == 0 && q == 0) {
return -1;
}
queue
q.push(make_pair(x1, y1));
bool visited[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
visited[i][j] = false;
}
}
int distance[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
distance[i][j] = -1;
}
}
distance[x1][y1] = 0;
int moves[8][2] = {{p, q}, {-p, q}, {p, -q}, {-p, -q}, {q, p}, {-q, p}, {q, -p}, {-q, -p}};
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 8; i++) {
int newX = x + moves[i][0];
int newY = y + moves[i][1];
if (validMove(newX, newY, m, n) && !visited[newX][newY]) {
visited[newX][newY] = true;
distance[newX][newY] = distance[x][y] + 1;
q.push(make_pair(newX, newY));
if (newX == x2 && newY == y2) {
return distance[newX][newY];
}
}
}
}
return -1;
}
int main() {
int m, n, p, q, x1, y1, x2, y2;
cin >> m >> n >> p >> q >> x1 >> y1 >> x2 >> y2;
int result = minMoves(m, n, p, q, x1, y1, x2, y2);
cout << result << endl;
if (result != -1) {
int distance = result;
int moves[8][2] = {{p, q}, {-p, q}, {p, -q}, {-p, -q}, {q, p}, {-q, p}, {q, -p}, {-q, -p}};
int x = x1;
int y = y1;
cout << x << " " << y << endl;
while (distance > 0) {
for (int i = 0; i < 8; i++) {
int newX = x + moves[i][0];
int newY = y + moves[i][1];
if (validMove(newX, newY, m, n) && distance - 1 == minMoves(m, n, p, q, newX, newY, x2, y2)) {
x = newX;
y = newY;
distance--;
cout << x << " " << y << endl;
break;
}
}
}
}
return 0;
}
```
Таким образом, программа считывает входные данные, вызывает функцию "minMoves" для определения минимального числа ходов и выводит результат. Если (p, q)-лошадь не может достичь конечной клетки, программа выводит -1. Если (p, q)-лошадь может достичь конечной клетки, программа последовательно выводит положения (p, q)-лошади на этом пути.