## Editorial for Horse Matrix

**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.**

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