Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
893 B
0
Indexable
Never
int KnightWalk(int N, int Sx, int Sy, int Fx, int Fy)
{
    Sx--, Sy--, Fx--, Fy--;

    int ans = -1;

    pair<int, int> mv[] = {{1, 2}, {1, -2}, {2, 1}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};

    int vis[N][N];
    memset(vis, -1, sizeof(vis));

    queue<pair<int, int>> q;

    q.push({Sx, Sy});
    vis[Sx][Sy] = 0;

    while (q.size())
    {
        auto a = q.front();
        q.pop();

        int x = a.first, y = a.second, curr = vis[x][y];

        if (x == Fx && y == Fy)
        {
            ans = curr;
            break;
        }

        for (auto i : mv)
        {
            int x1 = x + i.first, y1 = y + i.second;

            if (x1 < 0 || y1 < 0 || x1 >= N || y1 >= N || vis[x1][y1] != -1)
                continue;

            vis[x1][y1] = curr + 1;
            q.push({x1, y1});
        }
    }

    return ans;
}
Leave a Comment