Interview Question
Country: India
#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;
}
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;
}
I don't understand how it can work ? There is only one move considered (-1,-2)... There is no check for out of bound either. Try to run with: 0,0,7,7 for instance.
Looks like a perfect candidate for BFS:
- Joker.eph January 18, 2014