6
\$\begingroup\$

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';
    }
}
\$\endgroup\$
  • \$\begingroup\$ How was the performance and memory usage? \$\endgroup\$ – pacmaninbw Jul 9 '16 at 15:37
2
\$\begingroup\$
  • 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.