Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.1 kB
3
Indexable
Never
#define F first
#define S second
bool check(int x, int y, int n) {
    if(x > n || y > n || x <= 0 || y <= 0)
        return false;
    return true;
}
// we can make moves like this it will help in code quality.
vector<vector<int>> moves{{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};

int knightWalk(int n, pair<int,int> &s, pair<int,int> &e) {
    vector<vector<int>> m(n+1, vector<int>(n+1, INT_MAX));
    m[s.F][s.S] = 0;

    queue<pair<int,int>> q;
    q.push(s);
    int move = 0;
    while(!q.empty())
    {
        int size = q.size();
        for(int i=0; i<size; ++i)
        {
            pair<int,int> f = q.front();
            q.pop();

            if(f == e) return move;

            for(int j=0; j<8; ++j)
            {
                int x = f.F + moves[j][0], y = f.S + moves[j][1];

                if(check(x, y, n) && m[x][y] > m[f.F][f.S] + 1)
                {
                    m[x][y] = m[f.F][f.S] + 1;

                    q.push({x, y});
                }
            }
        }
        ++move;
    }
    return move;
}