# Shortest knight path

In preparing a review of this question, I decided to rewrite the code from scratch using a more object oriented approach as I suggested in my review.

To recapitulate the problem statement, we are given an input such as the following:

6 5
. s . . .
. d . . .
. . x . .
. . x . .
. . . . .
. . . . .


The two integers are the number of rows and columns respectively, and the lines that follow are the board to be examined. A knight is placed at starting point s and must travel to the destination at d without landing on any occupied squares (denoted by x). Open squares are marked with . and whitespace must separate each square in the input.

The output of the program is the minimum number of valid knight moves to get from s to d or the word "NO" if there is no path. The search uses a simple breadth first search. Each call to validMoves generates a std::vector of all unvisited squares that can be reached with one move of a knight originating on any of the squares indicated in the input std::vector moves.

The algorithm terminates when either there are no valid moves left or a path has been found to the destination.

I'm interested in a general review, but in particular, the repeated calls to tryMove() seem somewhat inelegant to me, but I didn't come up with anything that I thought was better.

## knight.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>

class Board
{
public:
Board(int n, int m) :
start{ERR},
finish{ERR},
rows{n},
cols{m},
map{new char[rows*cols]}
{}
virtual ~Board() { delete[] map; }
int mindistance() const {
if (finish == ERR || start == ERR) {
return ERR;
}
return measure(start, finish);
}
friend std::istream& operator>>(std::istream& in, Board &b) {
int a = 0;
for (int i = b.rows; i; --i) {
for (int j = b.cols; j; --j, ++a) {
in >> b.map[a];
switch(b.map[a]) {
case STARTCHAR:
if (b.start != ERR) {
throw std::runtime_error("Duplicate start character detected");
}
b.start = a;
break;
case ENDCHAR:
if (b.finish != ERR) {
throw std::runtime_error("Duplicate finish character detected");
}
b.finish = a;
break;
case BLOCKEDCHAR:
case OPENCHAR:
break;
default:
throw std::runtime_error("Unknown character detected");
}
}
}
return in;
}
static constexpr char STARTCHAR = 's';
static constexpr char ENDCHAR = 'd';
static constexpr char BLOCKEDCHAR = 'x';
static constexpr char OPENCHAR = '.';
static constexpr int ERR = -1;
private:
int measure(int here, int there) const {
std::vector<bool> visited(cols * rows, false);
int distance = 0;
for (std::vector<int> moves{here}; moves.size(); moves = validMoves(visited, moves)) {
if (moves.end() != std::find(moves.begin(), moves.end(), there)) {
return distance;
}
++distance;
}
return ERR;
}
void tryMove(int x, int y, std::vector<bool>& visited, std::vector<int>& result) const {
if (isValid(x, y)) {
int a=addr(x, y);
if (!visited[a]) {
visited[a] == true;
result.push_back(a);
}
}
}
std::vector<int> validMoves(std::vector<bool>& visited, std::vector<int>& moves) const {
std::vector<int> result;
// create a vector of all possible moves
for (auto m : moves) {
int x = getX(m);
int y = getY(m);
visited[m] = true;
// eight possible moves
tryMove(x+1, y+2, visited, result);
tryMove(x+1, y-2, visited, result);
tryMove(x-1, y+2, visited, result);
tryMove(x-1, y-2, visited, result);
tryMove(x+2, y+1, visited, result);
tryMove(x+2, y-1, visited, result);
tryMove(x-2, y+1, visited, result);
tryMove(x-2, y-1, visited, result);
}
return result;
}
int addr(int x, int y) const {
return x + y * cols;
}
int getX(int here) const {
return here % cols;
}
int getY(int here) const {
return here / cols;
}
bool isValid(int x, int y) const {
if (x < 0 || y < 0 || x >= cols || y >= rows)
return false;
return (map[addr(x, y)] != BLOCKEDCHAR);
}

/* for 4 row x 5 col matrix, we have:
*
*  0  1  2  3  4
*  5  6  7  8  9
* 10 11 12 13 14
* 15 16 17 18 19
*
* so getX(11) = 1 and getY(11) = 2
* and getX(4) = 4 and getY(4) = 0
* and getX(17) = 2 and getY(17) = 3
*/
int start;
int finish;
int rows;
int cols;
char *map;
};

int main()
{
int n, m;
std::cin >> n >> m;
Board board(n, m);
try {
std::cin >> board;
}
catch (std::runtime_error& e) {
std::cout << e.what() << ": Terminating program\n";
return 1;
}
int distance = board.mindistance();
if (distance == Board::ERR) {
std::cout << "NO\n";
} else {
std::cout << distance << '\n';
}
}

• How was the performance and memory usage? – pacmaninbw Jul 9 '16 at 15:37

## 1 Answer

• A standard way to loop over a regular set of moves is to prepare an array of deltas:

    using square = std::pair<int, int>;
std::vector<square> deltas = {
{1, 2}, {1, -2}, {-1, 2}, {-1, -2},
{2, 1}, {2, -1}, {-2, 1}, {-2, -1}
};

for (auto delta: deltas) {
tryMove(x + delta.first, y + delta.second);
}

• It feels that std::pair<int, int> generally represents a square better than a single integer.

• Well, a const static square deltas[] would be simpler and possibly more efficient... – Deduplicator Jul 19 '17 at 16:57