CareerCup

Looks like a perfect candidate for BFS:

#include <queue>
#include <vector>

#include "gtest/gtest.h"

struct Position {
    int x;
    int y;

};
Position operator+(const Position &p1, const Position &p2) {
    return Position{ p1.x+p2.x, p1.y+p2.y };
}
bool operator==(const Position &p1, const Position &p2) {
    return p1.x==p2.x && p1.y==p2.y ;
}

// Breadth First Search
template<int N>
int knightReachability(Position src, Position dst) {
    if(src == dst)
        return 0;

    // Keep track of which cell has been visited
    bool visited[N][N]{};

    // Keep on the stack the next Positions to visit and the count for each
    std::queue<std::pair<Position, int>> nextToCheck;

    nextToCheck.push({src, 0});

    std::vector<Position> knightMoves = {
            { 1, 2 }, { 2, 1 },
            { 2, -1 }, { 1, -2 },
            { -1, -2 }, { -2, -1 },
            { -2, 1}, { -1, 2 }
    };

    auto isValidPos = [] (const Position &pos) -> bool {
        return pos.x>0 && pos.y>0 && pos.x<N && pos.y<N;
    };

    while(!nextToCheck.empty()) {
        Position currentPos;
        int currentCount;
        std::tie(currentPos, currentCount) = nextToCheck.front();
        nextToCheck.pop();
        visited[currentPos.y][currentPos.x] = true;
        for(const auto &move : knightMoves) {
            Position newPos = move + currentPos;
            if(newPos == dst)
                return currentCount+1;
            if(!visited[newPos.y][newPos.x] && isValidPos(newPos)) {
                nextToCheck.push({newPos,  currentCount+1});
            }
        }
    }
    // Should not be reached
    assert(0 && "The impossible happened !");
    return 0;
};



TEST(Chess, knightReachability) {
    EXPECT_EQ(0, knightReachability<8>({0,0}, {0,0}));
    EXPECT_EQ(1, knightReachability<8>({0,0}, {2,1}));
    EXPECT_EQ(2, knightReachability<8>({0,0}, {4,2}));
    EXPECT_EQ(6, knightReachability<8>({0,0}, {7,7}));
    EXPECT_EQ(6, knightReachability<8>({7,7}, {0,0}));
    EXPECT_EQ(2, knightReachability<8>({3,4}, {4,3}));
}

#include<iostream>
#include<queue>
#include<vector>
#include<climits>

#define MIN 0
#define MAX 7

using namespace std;

class Position
{
    public:
        int x;
        int y;

        Position()
        {}

        Position(int f, int s)
        {
            x = f;
            y = s;
        }

        Position operator+(const Position &incr)
        {
            Position new_pos;
            new_pos.x = this->x+incr.x;
            new_pos.y = this->y+incr.y;
            return new_pos;
        }

        bool operator==(const Position &dest)
        {
            if(this->x == dest.x && this->y == dest.y)
                return true;
            return false;
        }

        bool is_valid()
        {
            if(this->x < MIN || this->y < MIN || this->x > MAX || this->y > MAX)
                return false;
            return true;
        }
};
struct classcomp
{
    bool operator()(const Position &p1, const Position &p2)
    {
        if(p1.x == p2.x && p1.y == p2.y)
            return 0;
        return p1.x<p2.x;
    }
};

int find_closest_path(Position knight, Position king)
{
    if(!knight.is_valid() || !king.is_valid())
        return INT_MAX;
    if(knight == king)
        return 0;
    vector<pair<int, int> >moves(8);
    moves[0].first = 2;
    moves[0].second = -1;
    moves[1].first = 2;
    moves[1].second = 1;
    moves[2].first = 1;
    moves[2].second = -2;
    moves[3].first = 1;
    moves[3].second = 2;
    moves[4].first = -1;
    moves[4].second = 2;
    moves[5].first = -1;
    moves[5].second = -2;
    moves[6].first = -2;
    moves[6].second = 1;
    moves[7].first = -2;
    moves[7].second = -1;

    queue<Position>Q;
    bool visited[MAX+1][MAX+1] = {false};
    Q.push(knight);
    int curr_level = 1;
    int next_level = 0;
    int no_of_steps = 1;
    while(!Q.empty())
    {
        Position top = Q.front();
        for(int i=0; i<moves.size(); i++)
        {
            Position next = Position(moves[i].first, moves[i].second);
            Position curr = top + next;
            if(!curr.is_valid())
                continue;
            if(curr == king)
                return no_of_steps;
            if(visited[curr.x][curr.y] == false)
                visited[curr.x][curr.y] = true;
            else
                continue;
            Q.push(curr);
            next_level++;
        }
        Q.pop();
        curr_level--;
        if(curr_level == 0)
        {
            no_of_steps++;
            curr_level = next_level;
            next_level = 0;
        }
    }
    return -1;
}

int main()
{
    Position knight(0, 0);
    Position king(7,7);

    int no_of_moves = find_closest_path(knight, king);
    cout<<"no of moves required are - "<<no_of_moves<<endl;
    return 0;
}

Why are you all mad to write code before explaining logic. Code is junk. Any college 1st or 2nd yr guy can do. Give out logic first.

pseudocode:

bt(current, target, num_moves, min_so_far)
{
	if(current==target)
	{
		if(num_moves<min_so_far)
			min_so_far = num_moves
		return min_so_far
	}
	
	if(num_moves>min_so_far)
		return min_so_far
	
	candidates = get_candidates(current)
	
	foreach(candidate in candidates)
	{
		min_so_far = bt(candidate, target, num_moves+1, min_so_far)
	}
	return min_so_far
}

class KnightKing {
	boolean[][] visited = new boolean[8][8];
	int min = -1;

	public int catchTheKing (int knX, int knY, int kgX, int kgY) {
		min = -1;
		catchTheKing (knX, knY, kgX, kgY, 0);
		return min;
	}
	
	private void catchTheKing (int knX, int knY, int kgX, int kgY, int len) {
		if (visited[knX][knY]) return;
		if (knX == kgX && knY == kgY) {
			if (min == -1 || min > len) min = len;
			return;
		}
		visited[knX][knY] = true;
		if (knX > 0 && knY > 1) catchTheKing(knX-1, knY-2, kgX, kgY, len+1);
		// repeat the above for other moves as well
		visited[knX][knY] = false;
	}