Joker.eph
BAN USERLooks 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}));
}
Your first line is 6 times the same solution.
- Joker.eph January 21, 2014Your two last lines are also only one solution.