Infinite Chess
Contest: 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2800
Tags: implementation, shortest paths

The black king lives on a chess board with an infinite number of columns (files) and $$$8$$$ rows (ranks). The columns are numbered with all integer numbers (including negative). The rows are numbered from $$$1$$$ to $$$8$$$.

Initially, the black king is located on the starting square $$$(x_s, y_s)$$$, and he needs to reach some target square $$$(x_t, y_t)$$$. Unfortunately, there are also white pieces on the board, and they threaten the black king. After negotiations, the white pieces agreed to let the black king pass to the target square on the following conditions:

- each turn, the black king makes a move according to the movement rules;
- the black king cannot move to a square occupied by a white piece;
- the black king cannot move to a square which is under attack by any white piece. A square is under attack if a white piece can reach it in one move according to the movement rules;
- the white pieces never move.

Help the black king find the minimum number of moves needed to reach the target square while not violating the conditions. The black king cannot leave the board at any time.

The black king moves according to the movement rules below. Even though the white pieces never move, squares which they can reach in one move are considered to be under attack, so the black king cannot move into those squares.

Below are the movement rules. Note that the pieces (except for the knight) cannot jump over other pieces.

- a king moves exactly one square horizontally, vertically, or diagonally.
- a rook moves any number of vacant squares horizontally or vertically.
- a bishop moves any number of vacant squares diagonally.
- a queen moves any number of vacant squares horizontally, vertically, or diagonally.
- a knight moves to one of the nearest squares not on the same rank, file, or diagonal (this can be thought of as moving two squares horizontally then one square vertically, or moving one square horizontally then two squares vertically — i. e. in an "L" pattern). Knights are not blocked by other pieces, they can simply jump over them.

There are no pawns on the board.

King and knight possible moves, respectively. Dotted line shows that knight can jump over other pieces.

Queen, bishop, and rook possible moves, respectively.

Input format:
The first line contains two integers $$$x_s$$$ and $$$y_s$$$ ($$$1 \le x_s \le 10^8$$$; $$$1 \le y_s \le 8$$$) — the starting coordinates of the black king.

The second line contains two integers $$$x_t$$$ and $$$y_t$$$ ($$$1 \le x_t \le 10^8$$$; $$$1 \le y_t \le 8$$$) — the coordinates of the target square for the black king.

The third line contains one integer $$$n$$$ ($$$0 \le n \le 2000$$$) — the number of white pieces on the board.

Then $$$n$$$ lines follow, the $$$i$$$-th line contains one character $$$t_i$$$ and two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le 10^8$$$; $$$1 \le y_i \le 8$$$) — the type and the coordinates of the $$$i$$$-th white piece. The types of pieces are represented by the following uppercase Latin letters:

- K — king
- Q — queen
- R — rook
- B — bishop
- N — knight

There can be any number of white pieces of any type listed above on the board, for example, $$$3$$$ white kings or $$$4$$$ white queens. There are no pawns on the board.

Additional constrains on the input:

- no square is occupied by more than one white piece;
- the starting square for the black king is different from the square he wants to reach, and neither of these two squares is occupied or is under attack by any white piece.

Output format:
Print one integer — the minimum number of moves needed for the black king to reach the target square while not violating the conditions, or $$$-1$$$ if it is impossible.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
The image below demonstrates the solution for the second example. Here, the letters K, R, s, and t represent the white king, the white rook, the starting square, and the target square, respectively. Bold crosses mark the squares which are under attack by the white pieces. Bold dots show the shortest path for the black king.

Example input:
1 8
7 8
2
N 4 8
B 4 6

Example output:
10

Example input:
1 1
1 5
2
K 1 3
R 2 3

Example output:
6

Editorial:
First, we can limit the field to a non-infinite amount of columns. Take the leftmost position, the rightmost one and leave like $$$10$$$ more cells from each side so that everything is nice on the borders.
If the field wasn't as huge, we could just do a BFS over it. Mark the cells that are taken by the pieces and that are attacked by them. Then just go and avoid them. Unfortunately, the field is like $$$10^9$$$ cells large, and we also have up to $$$8$$$ transitions from each cell. Too much.
Let's use the fact that there are not too many pieces on the board. Take a look at two pieces that have only empty columns between them. If you go far enough inwards, then all the columns between them will look the same in terms of cells to be avoided. That far enough is the columns at distance more than $$$8$$$ from both of the pieces. The only pieces that can possibly affect these columns are rooks or queens far way that fill the entire rows.
Since these columns are the same, let's get rid of them and account for the distance by using a Dijkstra instead of a BFS.
The solution becomes the following. Leave only the columns that have a piece at distance at most $$$8$$$ from them. There will be at most $$$16 \cdot n$$$ of them. Mark all the attacked cells on the taken columns. Do Dijkstra and carefully handle the moves over the missing columns.
Let's think more about moving over the missing columns. Let the distance between adjacent taken columns be $$$d$$$. Then the king can go from some row $$$i$$$ of the first column into some row $$$j$$$ of the second column in $$$max(|i - j|, d)$$$ moves (it can save moves by going diagonally). You can code it exactly like that, but you can also do it a little neater. Leave not $$$8$$$ but $$$16$$$ columns. Now, the moves that the king saves by going diagonally will be accounted for automatically. And you can only consider going to the previous, the current or the next row for any pair of adjacent columns.