Knight Walk

Given a square chessboard, the initial position of Knight and position of a target. Find out the minimum steps a Knight will take to reach the target position.

Note:

The initial and the target position co-ordinates of Knight have been given accoring to 1-base indexing.

• Time : O(n^2)
• Space : O(n^2)

c++

class Solution {
    inline int distance(vector<int>& target, int& y, int& x) {
        return abs(y - target[0]) + abs(x - target[1]); 
    }
public:
    int minStepToReachTarget(vector<int>&k, vector<int>&t, int N){
        if(k == t) return 0;
        const int hash = 1e4;
        unordered_set<int> vis1, vis2;
        queue<pair<int, int>> q1, q2;
        int res = 1;
        int dy[8]{-1, -2, -2, -1, 1, 2, 2, 1}, dx[8]{-2, -1, 1, 2, 2, 1, -1, -2};
        vis1.insert((k[0]-1) * hash + (k[1]-1));
        vis2.insert((t[0]-1) * hash + (t[1]-1));
        q1.push({k[0]-1, k[1]-1});
        q2.push({t[0]-1, t[1]-1});
        
        while(!q1.empty() and !q2.empty()) {
            auto& q = q1.size() < q2.size() ? q1 : q2;
            auto& vis = q1.size() < q2.size() ? vis1 : vis2;
            auto& ovis = q1.size() < q2.size() ? vis2 : vis1;
            auto& o = q1.size() < q2.size() ? t : k;
            
            int sz = q.size();
            
            while(sz--) {
                auto p = q.front(); q.pop();
                auto y = p.first, x = p.second;
                for(int i = 0; i < 8; i++) {
                    int ny = y + dy[i], nx = x + dx[i];
                    int key = ny * hash + nx;
                    if(0 <= ny and ny < N and 0 <= nx and nx < N and !vis.count(key)) {
                        if(ovis.count(key)) return res;
                        if(distance(o, y, x) + 1 < distance(o, ny, nx)) continue;
                        vis.insert(key);
                        q.push({ny, nx});
                    }
                }
            }
            
            res++;
        }
        
        
        return -1;
    }
};