Problem Statement

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.

Example 1:

Input:
N=6
knightPos[ ] = {4, 5}
targetPos[ ] = {1, 1}
Output:
3
Explanation:Knight takes 3 step to reach from
(4, 5) to (1, 1):
(4, 5) -> (5, 3) -> (3, 2) -> (1, 1).

Problem Link

Steps by Knight | Practice | GeeksforGeeks

Code

class Solution 
{
    public:
    //Function to find out minimum steps Knight needs to reach target position.
	int minStepToReachTarget(vector<int>&KnightPos,vector<int>&TargetPos,int N)
	{
	    int srR = KnightPos[0]-1;
	    int srC = KnightPos[1]-1;
	    
	    int desR = TargetPos[0]-1;
	    int desC = TargetPos[1]-1;
	    
	    queue<pair<int,int>> q;
	    int depth = 0;
	    vector<vector<bool>> visited(N+1,vector<bool>(N+1,false));
	    q.push({srR,srC});
	    visited[srR][srC] = true;
	    
	    
	    while(!q.empty())
	    {
	        
	        int lsize = q.size();
	        
	        while(lsize--)
	        {
	            auto p = q.front();
	            int x = p.first;
	            int j = p.second;
	            q.pop();
	            if(x==desR && j==desC)
	            return depth;
	            
	            if(x+2<=N-1 && j-1>=0 && !visited[x+2][j-1])
	            {
	                q.push({x+2,j-1});
	                visited[x+2][j-1] = true;
	            }
	            
	            if(x+2<=N-1 && j+1<=N-1 && !visited[x+2][j+1])
	            {
	                q.push({x+2,j+1});
	                visited[x+2][j+1] = true;
	            }
	            
	            if(x-2>=0 && j-1>=0 && !visited[x-2][j-1])
	            {
	                q.push({x-2,j-1});
	                visited[x-2][j-1] = true;
	            }
	            
	            if(x-2>=0 && j+1<=N-1 && !visited[x-2][j+1] )
	            {
	                q.push({x-2,j+1});
	                visited[x-2][j+1] = true;
	            }
	            
	            if(x-1>=0 && j-2>=0 && !visited[x-1][j-2])
	            {
	                q.push({x-1,j-2});
	                visited[x-1][j-2] = true;
	            }
	            
	            if(x+1<=N-1 && j-2>=0 && !visited[x+1][j-2])
	            {
	                q.push({x+1,j-2});
	                visited[x+1][j-2] = true;
	            }
	            
	            if(x+1<=N-1 && j+2<=N-1 && !visited[x+1][j+2])
	            {
	                q.push({x+1,j+2});
	                visited[x+1][j+2] = true;
	            
	            }
	            if(x-1>=0 && j+2<=N-1 && !visited[x-1][j+2])
	            {
	                q.push({x-1,j+2});
	                visited[x-1][j+2] = true;
	            }
	       }
	        
	        depth++;
	    }
	    return depth;
	    
	}
};