Editorial for Horse Matrix


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.
by: kon.simeonov

Let the board cells be nodes and horse moves from a cell to another cell be edges between nodes. In that context, the square matrix can be regarded as an undirected graph. Since every edge is a single horse move, all edges are equal, meaning that the graph is not weighted. The problem can be phrased as "find the shortest path between the start and end nodes, where the path consists of valid horse moves within the matrix". Valid horse moves would be moves that are inside the matrix and not on an impassable cell.

An appropriate algorithm to find the shorted path in an undirected unweighted graph would be BFS (breadth first search), because it always picks the nearest nodes to the current node.

The solution would be to run a BFS from the starting node until either the end node is reached or there are no more nodes that are not yet visited. Since the graph is undirected, the solution should also account for cycles in the graph - visited nodes should be marked to avoid being stuck in an infinite loop.

Some helpful notes
  • A 2-dimensional array is an appropriate way to store the cells. There is no need for adjacency list/matrix.
  • Marking cells as visited can be done by marking a cell with a 'x', once the cell has been visited. It can also be done using a set, but for this particular scenario, marking with 'x' is simpler and faster.
Pseudocode solution
def find_shortest(start_row, start_col, board)
    queue
    start = vertex(start_row, stack_col, 0)
    queue.enqueue(start)

    while queue not empty
        (row, col, steps) = queue.dequeue()

        for each move of get_valid_moves(row, col, board)
            (new_row, new_col) = move
            if is_end_node(new_row, new_col, board)
                return steps + 1
            else if is_visited(new_row, new_col, board)
                skip

            mark_as_visited(new_row, new_col, board)
            enqueue(vertex(new_row, new_col, steps + 1))

    return -1
Sample C++ solution
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#include <tuple>

constexpr std::array<std::pair<int, int>, 8> deltas = {
    {
        {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
        {2, -1}, {2, 1}, {1, -2}, {1, 2}
    }
};

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);

    using node = std::tuple<int, int, int>; // row, column, steps to reach the node
    int n;
    std::cin >> n;

    // since N <= 500, total number of cells will always be < 250000
    // which means the whole board can be read into a matrix
    std::vector<std::vector<char>> board(n);

    int start_row, start_col;
    for(int i = 0; i < n; ++i) {
        board[i].resize(n);
        for(int j = 0; j < n; ++j) {
            std::cin >> board[i][j];

            // keep track of the start
            if(board[i][j] == 's') {
                start_row = i;
                start_col = j;
            }
        }
    }

    std::queue<node> nodes;
    // put the starting node in the queue
    nodes.emplace(start_row, start_col, 0);

    // while there are still nodes to traverse
    while(nodes.size()) {
        const auto [r, c, steps] = nodes.front();
        nodes.pop();

        // calcuate valid moves and use them to push nearest cells into the queue
        for(const auto [dr, dc] : deltas) {

            // calculate next cell location
            const auto nr = r + dr;
            const auto nc = c + dc;

            // skip if
            if(nr < 0 || n <= nr || nc < 0 || n <= nc // outside the field
                || board[nr][nc] == 'x' // unpassable or visited
            ) continue;

            // if end, print result and stop execution
            if(board[nr][nc] == 'e') {
                std::cout << steps + 1 << std::endl;
                return 0;
            }

            // if not end mark as visited and push into the queue
            board[nr][nc] = 'x';
            nodes.emplace(nr, nc, steps + 1);
        }
    }

    // if end was not found
    std::cout << "No" << std::endl;
}

Comments

There are no comments at the moment.