anonymoose
BAN USERC++ 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;
}
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