Решение о путешествии Найта дает неправильный результат?
Путешествие рыцарей, в котором нам указаны начальная/конечная точки и размер доски (n*n):
Найдите минимальные шаги, чтобы добраться до конца от начальной точки. Если пути нет, верните -1:
Я пробовал решить эту проблему с помощью DFS:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Cell {
public:
int x, y;
Cell(int x, int y) {
this->x = x;
this->y = y;
}
};
int count(vector<vector<int>>& board, int a, int b, int x, int y, int n) {
if (a >= n || b >= n || b < 0 || a < 0 || board[a][b] == 1) return 500;
if (a == x && b == y) return 0;
board[a][b] = 1;
int one = count(board, a + 2, b + 1, x, y, n) + 1;
int two = count(board, a + 2, b - 1, x, y, n) + 1;
int three = count(board, a - 2, b + 1, x, y, n) + 1;
int four = count(board, a - 2, b - 1, x, y, n) + 1;
int five = count(board, a + 1, b + 2, x, y, n) + 1;
int six = count(board, a + 1, b - 2, x, y, n) + 1;
int seven = count(board, a - 1, b + 2, x, y, n) + 1;
int eight = count(board, a - 1, b - 2, x, y, n) + 1;
board[a][b] = 0;
int minMoves = min({one, two, three, four, five, six, seven, eight});
return minMoves;
}
int minMovesRequired(int n, Cell start, Cell end) {
vector<vector<int>> board(n, vector<int>(n, 0));
int a = start.x-1;
int b = start.y-1;
int c = end.x-1;
int d = end.y-1;
int ans = count(board, a, b, c, d, n);
return (ans >= 500) ? -1 : ans;
}
int main() {
int n = 6;
Cell start(6, 1);
Cell end(2, 4);
int result = minMovesRequired(n, start, end);
cout << "Minimum moves required: " << result << endl;
return 0;
}
... но для этого ввода:
n: 6
start: 6, 1
end: 2, 4
... Я не получаю ожидаемого результата:
- ожидаемый результат:
3 - фактический вывод кода:
tle
Как мне вообще подойти к этому вопросу? Почему это неправильно?
Ваши координаты отсчитываются от единицы, а ваша «проверка безопасности» отсчитывается от нуля, поэтому count возвращает 500 немедленно, поскольку a == n при первом вызове.
изменил значения координат на индекс, отсчитываемый от нуля, int a=start.x-1; интервал b=start.y-1; интервал c=end.x-1; интервал d=end.y-1; теперь это дает результат.
Похоже, вы используете DFS вместо BFS, что лучше решает вашу проблему. Кроме того, вы смешали индексацию на основе 1 с индексацией на основе 0, что привело к некоторым проблемам.
Если вы используете DFS, вам фактически придется просмотреть КАЖДЫЙ маршрут от начала до конца, а затем найти лучший из них. Используйте BFS, и вы быстро посетите каждую клетку на доске и сможете остановиться, как только дойдете до конца. Вместо этого попробуйте решить проблему с помощью BFS.
На workat.tech вы отправляете свой код?
Да, я решал эту проблему в Work at Tech.
Хорошо. Вы проверили мой ответ?
Ответы 1
Я не получаю ожидаемый результат: ожидаемый результат: 3, фактический вывод кода: tle
Обратите внимание, что TLE означает превышение лимита времени. Это не означает, что ваш код в конечном итоге не выдаст правильный результат, но он не дошел до этой точки за отведенное время. Другими словами, выбранный вами алгоритм недостаточно эффективен. Ваш обход в глубину посетит все возможные пути от исходной ячейки по доске. Это быстро приведет к миллионам и миллиардам путей, уже для относительно небольших 𝑛.
Улучшения
Обход в ширину значительно улучшит эту ситуацию, поскольку здесь не имеет значения, насколько велика доска: если существует кратчайший путь длиной 𝑘, то BFS никогда не будет просматривать пути, длина которых превышает 𝑘.
Еще одним улучшением может быть использование алгоритма A*: этот обход может отдавать предпочтение путям, идущим в направлении цели, что позволяет быстрее найти ее.
Но наиболее эффективно наблюдать, что когда два поля находятся далеко друг от друга, существует математическая формула, которая может дать вам количество ходов. И вы можете отдельно рассматривать случаи, когда два поля расположены близко и когда они могут быть ограничены границами небольшой доски.
Определить формулу и все граничные случаи немного утомительно, но это хорошее упражнение.
Вот реализация:
int countMoves(int n, int ax, int ay, int bx, int by) {
// Mirror in order to get A in the first quadrant of the board
if (ax > n - 1 - ax) return countMoves(n, n - 1 - ax, ay, n - 1 - bx, by);
if (ay > n - 1 - ay) return countMoves(n, ax, n - 1 - ay, bx, n - 1 - by);
// Swap cells so A has the least X coordinate
if (ax > bx) return countMoves(n, bx, by, ax, ay);
int dx = bx - ax;
int dy = abs(ay - by);
// Mirror along diagonal to get that dx <= dy
if (dx > dy) return countMoves(n, ay, ax, by, bx);
int taxi = dx + dy;
int odd = taxi % 2;
// Identify different cases (like small boards and nearby cells):
return taxi == 0 ? 0 // Trivial case
// The center of a 3x3 board and All cells on a smaller board are isolated
: n < 3 || n == 3 && ((ax & ay) == 1 || (bx & by) == 1) ? -1
// An adjacent cell is reached in 3 steps
: taxi == 1 ? 3
// Distance 4: The two ends of the center column on 3x3; (0, 0)→(1, 1); and case on same diagonal:
: n == 3 && dx == 0 && ax == 1 || dx == dy && dx < 3 && ((ax | ay) == 0 || dx == 2) ? 4
// The two ends of the left column on 4x4 have distance 5:
: n == 4 && (ax | bx) == 0 && dy == 3 ? 5
// The two general cases:
: dy < 2 * dx ? ((taxi + 4 - 3*odd) / 6) * 2 + odd
: (( dy + 3 - 2*odd) / 4) * 2 + odd;
}
int minMovesRequired(int n, Cell start, Cell end) {
return countMoves(n, start.x - 1, start.y - 1, end.x - 1, end.y - 1);
}
Добро пожаловать в Stack Overflow. Пожалуйста, прочитайте справочный центр , пройдите экскурсию SO и прочитайте Как задать вопрос . Также, пожалуйста, прочитайте о как написать «идеальный» вопрос , особенно о его контрольном списке . Затем отредактируйте свой вопрос, чтобы улучшить его, например, расскажите нам о своей проблеме.