Решение о путешествии Найта дает неправильный результат? ⇐ C++

[Anonymous]

Путешествие рыцаря, в котором нам указаны начальная/конечная точки и размер доски (n*n):

Найдите минимальные шаги, которые нужно пройти. конец от начальной точки. Если пути нет, верните -1:



Я пробовал решить эту проблему с помощью DFS:

Код: Выделить всё

#include 
#include 
#include 
using namespace std;

class Cell {
public:
int x, y;
Cell(int x, int y) {
this->x = x;
this->y = y;
}
};

int count(vector& 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 board(n, vector(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 

Подробнее здесь: [url]https://stackoverflow.com/questions/78720632/knights-journey-solution-gives-incorrect-output[/url]