ronith
10/17/2018 - 3:31 AM

Minimum steps to reach target by a Knight

Given a square chessboard of N x N size, the position of Knight and position of a target is given. We need to find out minimum steps a Knight will take to reach the target position.

Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the square chessboard. The next line contains the X-Y coordinates of the knight. The next line contains the X-Y coordinates of the target. Output: Print the minimum steps the Knight will take to reach the target position. Constraints: 1<=T<=100 1<=N<=20 1<=knight_pos,targer_pos<=N

Example: Input: 2 6 4 5 1 1 20 5 7 15 20 Output: 3 9

Minimum steps to reach target by a Knight.cpp
content_copyfile_download
//https://www.geeksforgeeks.org/minimum-steps-reach-target-knight/
#include<bits/stdc++.h>
using namespace std;
struct cell {
    int x, y, dis;
    cell() {}
    cell (int a, int b, int c) {
        x= a;
        y= b;
        dis= c;
    }
};
bool safe(int x, int y, int N) { 
    return (x >= 0 && x < N && y >= 0 && y < N);
} 
int func (int n, int ox, int oy, int tx, int ty) {
    int dx[]= {-2, -2, -1, -1, 1, 1, 2, 2};
    int dy[]= {-1, 1, -2, 2, -2, 2, -1, 1};
    
    queue <cell> q;
    q.push(cell (ox, oy, 0));
    int a,b;
    cell p;
    bool visited[n][n]= {0};
    while (!q.empty()) {
        p= q.front();
        q.pop();
        if (p.x== tx && p.y== ty) 
            return p.dis;
        for (int i=0;i<8;i++) {
            a= p.x+dx[i];
            b= p.y+dy[i];
            
            if (safe(a,b,n) && !visited[a][b]) {
                visited[a][b]= 1;
                q.push(cell(a,b,p.dis+1));
            }
        }
    }
}
int main()
{
    int t;
    cin>>t;
    while (t-- >0) {
        int n, ox,oy,tx,ty;
        cin>>n>>ox>>oy>>tx>>ty;
        
        cout<< func(n,ox-1,oy-1,tx-1,ty-1)<<endl;
    }
	return 0;
}