CODEWITHSUNDEEP
c++
Tom Huibregtse
Tom Huibregtse

Reputation: 713

Easier way to write a conditional block for SPOJ NAKANJ - Minimum Knight Moves

I am working on the SPOJ problem Minimum Knight Moves. Right now I have a series of conditional statements when I am checking the possible moves from each cell to make sure that a knight would not be moving off the chess board.

 // test initialization of one cell (a1)
    int i = 1; //row: a
    int j = 1; //col: 1
    if (j-2 >= MIN_COL) { // left moves
        if (i+1 <= MAX_ROW) {
            neighbors.push_back(board[i+1][j-2]);
        }
        if (i-1 >= MIN_ROW) {
            neighbors.push_back(board[i-1][j-2]);
        }
    }
    if (j+2 <= MAX_COL) { // right moves
        if (i+1 <= MAX_ROW) {
            neighbors.push_back(board[i+1][j+2]);
        }
        if (i-1 >= MIN_ROW) {
            neighbors.push_back(board[i-1][j+2]);
        }
    }
    if (i+2 <= MAX_ROW) { // up moves
        if (j+1 <= MAX_COL) {
            neighbors.push_back(board[i+2][j+1]);
        }
        if (j-1 >= MIN_COL) {
            neighbors.push_back(board[i+2][j-1]);
        }
    }
    if (i-2 >= MIN_ROW) { // down moves
        if (j+1 <= MAX_COL) {
            neighbors.push_back(board[i-2][j+1]);
        }
        if (j-1 <= MIN_COL) {
            neighbors.push_back(board[i-2][j-1]);
        }
    }

Is there an easier way to implement this without having to hardcode a condition in for all eight possible moves? I just learned about bitboards and will look into them as a potential solution, but right now I am more interested in learning if there is a better way to code up the above block of conditional statements in C++.

Upvotes: 0

Views: 394

Answers (1)

Martin Bonner supports Monica
Martin Bonner supports Monica

Reputation: 28987

You have essentially 8 pieces of code which check the position is in range, and push_back if so. I would start by writing that as a function, and then call that eight times. It might involve more comparisons, but I expect the optimizer will remove most of them.

void MyClass::add_new_position(int i, int j)
{
    if (MIN_COL <= j && j <= MAX_COL  &&
        MAX_ROW <= i && i <= MAX_ROW)
    {
        neighbors.push_back(board[i][j]);
    }
}

 // test initialization of one cell (a1)
    int i = 1; //row: a
    int j = 1; //col: 1
    add_new_position(i-1,j-2);
    add_new_position(i+1,j-2);
    add_new_position(i-1,j+2);
    add_new_position(i+1,j+2);
    add_new_position(i-2,j-1);
    add_new_position(i+2,j-1);
    add_new_position(i-2,j+1);
    add_new_position(i+2,j+1);

Upvotes: 2

Related Questions