anonymoose
BAN USER
Comments (2)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
C++ solution is made with BFS and memoization. I keep track of the previous move that got me to the current square. I then move backwards from the end to print out the moves that were made.
We have to make sure that we don't make any moves that would cause the arrays to go out of bounds, hence all of the if statements.
struct Coord
{
int x = 0;
int y = 0;
Coord(int initX, int initY) :x(initX), y(initY){}
Coord(){}
bool visited = false;
};
void MinMoves(Coord start, Coord end, int size)
{
vector<vector<Coord>> minMoves(size, vector<Coord>(size, Coord()));
queue<Coord> moves;
start.visited = true;
moves.push(start);
while (!moves.empty())
{
Coord move = moves.front();
move.visited = true;
moves.pop();
if (move.x == end.x && move.y == end.y)
break;
if (move.x >= 2 && move.y >= 1 && !minMoves[move.x  2][move.y  1].visited)
{
minMoves[move.x  2][move.y  1] = move;
moves.push(Coord(move.x  2, move.y  1));
}
if (move.x >= 1 && move.y >= 2 && !minMoves[move.x  1][move.y  2].visited)
{
minMoves[move.x  1][move.y  2] = move;
moves.push(Coord(move.x  1, move.y  2));
}
if (move.x >= 2 && move.y <= size  2 && !minMoves[move.x  2][move.y + 1].visited)
{
minMoves[move.x  2][move.y + 1] = move;
moves.push(Coord(move.x  2, move.y + 1));
}
if (move.x >= 1 && move.y <= size  3 && !minMoves[move.x  1][move.y + 2].visited)
{
minMoves[move.x  1][move.y + 2] = move;
moves.push(Coord(move.x  1, move.y + 2));
}
if (move.x <= size  3 && move.y >= 1 && !minMoves[move.x + 2][move.y  1].visited)
{
minMoves[move.x + 2][move.y  1] = move;
moves.push(Coord(move.x + 2, move.y  1));
}
if (move.x <= size  2 && move.y >= 2 && !minMoves[move.x + 1][move.y  2].visited)
{
minMoves[move.x + 1][move.y  2] = move;
moves.push(Coord(move.x + 1, move.y  2));
}
if (move.x <= size  3 && move.y <= size  2 && !minMoves[move.x + 2][move.y + 1].visited)
{
minMoves[move.x + 2][move.y + 1] = move;
moves.push(Coord(move.x + 2, move.y + 1));
}
if (move.x <= size  2 && move.y <= size  3 && !minMoves[move.x + 1][move.y + 2].visited)
{
minMoves[move.x + 1][move.y + 2] = move;
moves.push(Coord(move.x + 1, move.y + 2));
}
}
Coord cur = end;
while (cur.x != start.x && cur.y != start.y)
{
cout << cur.x << ", " << cur.y << endl;
cur = minMoves[cur.x][cur.y];
}
cout << cur.x << ", " << cur.y << endl;
}

anonymoose
January 20, 2015 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
It seems like this can be answered much more simply than it looks. We can simply keep track of all visited nodes in a hash table. Then traverse the linked list looking for visited nodes, keeping track of connected sequences.
 anonymoose February 04, 2015