c++graphdepth-first-searchbreadth-first-search

Knight's journey solution gives incorrect output?


The knights journey where we are given the start/end points and the size of board(n*n):

Find the minimum steps to reach the end from the starting point. If no path is there return -1:

image

I've tried solving it with 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;
}

...but for this input:

n: 6 
start: 6, 1 
end: 2, 4

...I am not getting the expected output:

How should i even approach this ques? Why is this wrong?


Solution

  • I am not getting the expected output: expected output: 3, actual code output: tle

    Note that TLE stands for Time Limit Exceed. It does not mean that your code would not eventually output the correct result, but that it didn't get to that point in the allotted time. In other words, the algorithm you have chosen is not efficient enough. Your depth-first traversal will visit all possible paths from the source cell across the board. This will quickly run into the millions and billions of paths, already for relatively small 𝑛.

    Improvements

    A breadth-first traversal would improve much on this, as there it doesn't matter how large the board is: if there is a shortest path of length 𝑘, then BFS will never look into paths that are longer than 𝑘.

    Another improvement could be to use an A* algorithm: this traversal could favour paths that go into the direction of the target, finding it sooner.

    But the most efficient is to observe that when the two fields are far appart, there is a mathematical formula that can give you the number of moves. And you can deal separately with cases where the two fields are close and where they might be limited by the boundaries of a small board.

    It is a bit tedious to identify a formula and all the boundary cases, but it is a nice exercise.

    Here is an implementation:

    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);
    }